Leetcode: Majority Element
This question is asked at Amazon and Rubrik, and we are going to learn a very special algorithm here. \
Given an array nums of size n, return the majority element of the array. The majority element is the element that appears ⌊n / 2⌋ or more times assuming that the majority element is always in the array.
In [3, 2, 3] the majority element is 3 since it occurs 2 times.
In [2, 1, 1, 1, 2, 2] the majority element is 2 since that appears 4 times, while 1 appears 3 times. I'll discuss 2 methods here: Divide and conquer and Boyce-Moore Algorithms, attempting to be coded and explained in C++.
If we know the majority element in the left and right halves of an array, we can determine the global majority element in linear time.
We can apply a divide and conquer approach that recurses on both the left and right halves of an array until an answer can be achieved. We will pass low and high indices that determines the slice of overall array, since simply passing indexes would take way too much time and effort to try to accomplish.
The majority element of length - 1 slice is its only element and we must combine answers on the left and right halves to see if they agree on the majority element. If they disagree, only one of them can be "right" so we need to count, and the overall answer for the array is the majority element inside of the array.
class Solution {
public:
int countInRange(vector<int>&nums, int num, int lo, int hi) {
//the occurance of a number inside of an array.
int count = 0;
for(int i = lo; i <= hi; i++) {
if(nums[i] == num) {
count++;
}
}
return count;
}
int majorityElementRec(vector<int>&nums, int lo, int hi) {
if(lo == hi) {
return nums[lo];
}
//calculate the middle
int mid = (hi - lo) / 2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid + 1, hi);
//see if the left element equals to the right element.
if(left == right) {
return left;
}
//count the number of left and right indices.
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
//see the count of both of these numbers.
if(leftCount > rightCount) {
return left;
}
return right;
}
int majorityElement(vector<int>& nums) {
return majorityElementRec(nums, 0, nums.size() - 1);
}
};
So what happened was that we recursively call the left and right end of the array and see the majority element in the left and right side and see if the left and right maximum occurrence are equal to each other and if they don't we count the element and see which ones has the greatest occurrence and we choose that element as the maximum. So it goes down and progressively goes up to see the greatest occurrence numbers.
The next algorithm is the Boyer-Moore Algorithm. We look for a suffix of nums where suf[0] is the majority element in the suffix. To do this, maintain a count, which is incremented whenever we see an instance of current candidate for majority element and decremented when we see anything else. If count equals 0 we forget about everything and consider the current number as the candidate for the majority element. Here's the solution:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int counter = 0;
int majority;
for(int num: nums) {
if(!counter) {
majority = num;
}
if (num == majority) {
counter = counter + 1;
} else {
counter = counter - 1;
}
}
}
};
Boyer moore tries alignments and for each alignment tries character comparisons and it skips many alignments that it does not need to examine. We keep a counter. We will cancel one element with another element if they are not equal. If the count becomes 0 we make the count 1 and includes the next corresponding element as the majority element.
We validate by counting the occurrence of the majority element. Then we make sure this number is greater than the total count of the set dividing by 2 and then see this works. Every time.
Comments
Post a Comment