Majority Element | InterviewBit | Solution Explained

I explain the solution to Majority Element on InterviewBit using visuals in simple words. NOT using the Boyer Moore algorithm.

0. Majority Element: Problem Discussion

0.0. IO Format

• input:
  • an array of integers of length N
• output:
  • the single element in the array which exists with a frequency of greater than N / 2.

0.1. Examples

The array given is [3,2,2,4,2,2]. The output is 2 because it exists with a frequency of 4, which is greater than N / 2 = 6 / 2 = 3.

1. Majority Element: Observations & Logic

1.0. Naïve solution

Well this question is quite dumb, isn’t it? Why not just create a frequency table and find the key with the value more than N / 2? Pretty easy.

The time complexity is O(N) to iterate over all the elements in the array and create a dictionary. The dictionary is of the size O(N) since we need to store counts of every single element.

1.1. O(1) Space?

Now, here the real question starts. Is there a way to do the same in O(1) space?

Well, once again you realize you can sort the array and simply iterate to find the longest continuous sequence of the same number. Too easy!

1.2. Interviewer: Can you do better?

But, now the interviewer asks you … can you do this in better time?

Well, think about it.

It is not so easy anymore. O(1) space and possibly O(N) on top of it?

1.3. The sneaky solution

The solution I present is not exactly O(N) time, but very close to it. The space complexity of my solution is O(1). And, I am not going to use the Boyer-Moore algorithm.

The solution relies on one single observation. I have talked about it numerous times on my YouTube channel as well.

Whenever you are cornered into places with very high restrictions on space, think in terms of bits.

1.4. Putting the bits together

The only thing we change here is the perspective. No fancy math or proofs or anything. We are just going to think of numbers in their binary representations, instead of their decimal representations.

Note that the question mentions how there is one element that is present with a frequency of > N / 2. This means that all the bits of the number are also present with a frequency of > N / 2.

Now we can start to build up our solution from 0.

Look at what happens at the rightmost column.

We see that the bits are overwhelmingly present with 0s. What does that mean? Since the 0 bits are a majority – present with a frequency of > N / 2, we can say that the majority element has a 0 in this bit!

Now, we continue on the other bits.

And look at what we have! The answer is 010 in binary or 2 in decimal.

2. Majority Element: Optimized Implementation

2.0. Code

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def majorityElement(self, A):
        # S: O(1)
        # T: O(log(w).N)

        n = len(A)
        ans = 0
        for b in range(32):
            ones = 0
            for num in A: # O(N)
                if (1 << b) & num: 
                    ones += 1
            
            if ones > n // 2:
                ans += (1 << b)

        return ans

2.1. Complexity Analysis

• Time: O(NlogW), N is the number of elements in A and W is the size of the word (integer in our case). Basically, the solution for only int is O(32N).
• Space: O(1), we only store the variables

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.