LeetCode: Majority Element

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.

1. 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 the candidate_count by 1 and making this element as our candidate. So, candidate_count=1 and candidate=2.
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 and candidate=2.
3. nums[2]=3, because the previous candidate_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 and candidate=3.
4. 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 and candidate=3.
5. nums[4]=1 because the previous candidate_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 and candidate=1.
6. 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 and candidate=1.
7. nums[6]=1 as the candidate_counter=0, let's start afresh and make this as our candidate. We will increase the candidate_counter by 1, making candidate_counter=1 and candidate=1.
8. nums[7]=1 as the elements match with our previous candidate, increase the candidate_counter by 1. candidate_counter=2 and candidate=1.
9. nums[8]=2 as the element doesn't match with our candidate, decrease the candidate_counter by 1. The counter become 1 from 2, so candidate_counter > 0 which means that the candidacy of 1 is still valid. candidate_counter=1 and candidate=1.
10. nums[9]=1 as the element and candidate match, increase the candidate_counter by 1. candidate_counter=2 and candidate=1.
11. nums[10]=1 element and candidate match, increase the candidate_counter by 1. candidate_counter=3 and candidate=1.
12. nums[11]=3 element and the candidate doesn't match, decrease the candidate_counter by 1. The candidate counter becomes 2 from 3. But because candidate_counter > 0 , the candidacy of 1 still valid. candidate_counter=2 and candidate=1.
13. nums[12] =1 element and candidate match, increase the candidate_counter by 1. Making the candidate_counter=3 and candidate=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.

Comments

[JMW]

Solution in KOTLIN with a single pass, O(n), through the array:

fun majorityElement(elements: Array<Int>): Int? {
    val freq = mutableMapOf<Int, Int>()
    val majorityCount = elements.count() / 2
    var majorityElement: Int? = null
    elements.forEach { element ->
        val count = freq.getOrDefault(element, 0) + 1
        if(count > majorityCount) {
            majorityElement = element
            return@forEach
        }
        freq[element] = count
    }
    return majorityElement
}