Problem Statement
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋
times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Solution Thought Process
The straight forward solution is to have a hash map to calculate the occurrence and then check if the occurrence is greater than ⌊ n/2 ⌋
times.
The space complexity is O(n) and time complexity is O(n).
But we can do better with space. We can make use of the fact that there will certainly a majority element in the array.
Let's say the array is,
nums: 2 1 3 1 1 2 1 1 2 1 1 3 1
idx: 0 1 2 3 4 5 6 7 8 9 10 11 12
Let's describe the algorithm. First, we have a counter for majority element, let's name it candidate_count
and let's call the majority element candidate
.
-
nums[0]=2
. For now, we know that this can be our majority element because we don't have processed any other entries before. Increasing thecandidate_count
by 1 and making this element as our candidate. So,candidate_count=1
andcandidate=2
. -
nums[1]=1
, when we get this, we are sure that 2 and 1 can't be majority elements for the elements we have processed. We will be decreasing the candidate counter by 1. So,candidate_count=0
andcandidate=2
. -
nums[2]=3
, because the previouscandidate_count
has been 0 (being demolished by the different element), we can start afresh and consider this element as a candidate and increase the candidate count.candidate_count=1
andcandidate=3
. -
nums[3]=1
, the element and candidate are different, which means that this number and the previous candidate doesn't have any chance for being the majority element. Decreasing the candidate counter by 1. So,candidate_counter=0
andcandidate=3
. -
nums[4]=1
because the previouscandidate_count
has been 0 (being demolished by the different element), we can again start afresh and consider this element as a candidate and increase the candidate count by 1.candidate_count=1
andcandidate=1
. -
nums[5]=2
the element doesn't match with our previous candidate, so we will decrease the candidate_counter by 1. So,candidate_counter=0
andcandidate=1
. -
nums[6]=1
as thecandidate_counter=0
, let's start afresh and make this as our candidate. We will increase the candidate_counter by 1, makingcandidate_counter=1
andcandidate=1
. -
nums[7]=1
as the elements match with our previous candidate, increase the candidate_counter by 1.candidate_counter=2
andcandidate=1
. -
nums[8]=2
as the element doesn't match with our candidate, decrease the candidate_counter by 1. The counter become1
from2
, socandidate_counter > 0
which means that the candidacy of1
is still valid.candidate_counter=1
andcandidate=1
. -
nums[9]=1
as the element and candidate match, increase thecandidate_counter
by 1.candidate_counter=2
andcandidate=1
. -
nums[10]=1
element and candidate match, increase thecandidate_counter
by 1.candidate_counter=3
andcandidate=1
. -
nums[11]=3
element and the candidate doesn't match, decrease thecandidate_counter
by 1. The candidate counter becomes2
from3
. But becausecandidate_counter > 0
, the candidacy of1
still valid.candidate_counter=2
andcandidate=1
. -
nums[12] =1
element and candidate match, increase thecandidate_counter
by 1. Making thecandidate_counter=3
andcandidate=1
.
So our candidate
is 1 which is ultimately our answer.
Can you assume why the candidate_counter
is 3 at the end of the loop?
If you count the non-majority elements, you can see that there are 5 of them. Each of the non-majority elements cancels out one frequency of the majority element. So, 5 non-majority elements cancel out 5 majority-elements from candidacy. How many majority elements remain in the array? The answer is 3, which at the end is the candidate_counter
.
With this algorithm, we can easily find the majority element.
Solution
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate_count = 0, candidate;
for(auto a:nums)
{
if(candidate_count == 0)
{
candidate = a;
candidate_count = 1;
}
else if(candidate == a)
{
candidate_count++;
}
else {
candidate_count--;
}
}
return candidate;
}
};
Complexity
Time Complexity: O(n), we are iterating over the array only once.
Space Complexity: O(1), we are not using any extra space.
Top comments (1)
Solution in KOTLIN with a single pass,
O(n)
, through the array: