Similar problem: LC 229. Majority Element II
Solving this question using a map that stores the frequency of each element is pretty straightforward. This problem is actually a very famous problem and an algorithm, Boyer Moore’s Majority Voting Element, has been devised to solve it. The algorithm works in O(n) time and O(1) space. Let’s have a look at it.
Idea: The algorithm goes over the whole array twice. In the first pass, we generate a single candidate value which is the majority value if there is a majority (thus, we have to check whether that value is actually the majority element in the next pass). The second pass simply counts the frequency of that value to confirm.
In the first pass, we need 2 values:
- A candidate value, initially set to any value.
- A count, initially set to 0.
Pseudocode (Python code):
num = 0
count = 0
for value in input:
if count == 0:
num = value
if num == value:
num += 1
else:
num -= 1
count = 0
for value in input:
if num == value:
count+=1
// return true if count > floor(input_size/2)
The actual question guarantees the existence of a majority element so we do not need the second pass. The actual solution should be:
int majorityElement(vector<int>& nums) {
// Boore's Majority Voting algorithm
int num=nums[0], count=1;
for (int i=1; i<nums.size(); i++)
if (nums[i] == num)
count++;
else if (count == 0)
num=nums[i], count=1;
else
count--;
return num;
}
Recommended: Check out the details of the majority voting algorithm https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html