# [Google Interview] How To Find The Majority Element In An Array?

Rate this post

[toc]

Company Tags: Google, Amazon, Yahoo, Microsoft

This is one of the Google interview questions and one of the most commonly asked questions during many interviews. So, can you give the optimal solution to this problem?

## Problem Formulation

Given an array `nums` of size` n`, the task is to return the majority element. The majority element is the element that appears more than [n / 2⌋ times.

Note: You may assume that the majority element always exists in the array.

⚠️Constraints:

1. `n = = nums.length`
2. `1 <= n <= 5 * 104`
3. `-231 <= nums[i] <= 231 – 1`

### ?Examples

Let’s have a look at some examples to improve our understanding of this problem.

## ?️Method 1: Brute Force Approach

Approach: The simplest solution to this problem would be to count the number of times every element occurs in nums. If this count is more than `(n/2)`, return the element.

Algorithm:

1. Initialize a couple of variables `count` and `max` that will store the count of an element and the count of the element that occurs maximum number of times in the list, respectively.
2. Iterate over the given list `nums` and increment the value of the `count` value if the same element appears again in the list.
3. Update the `max` variable when the value of the `count` variable is more than `max`. (Initially, the value of `count` will always be greater than `max`). Also, store the index of the element with the maximum count.
4. Finally, check if the `max > size//2`, return the element with the help of its index that you stored previously.

The following illustration will further clarify things:

Let’s look at the code:

```def majority_ele(nums):
size = len(nums)
max_count = 0
for i in range(size):
count = 0
for j in range(size):
if nums[i] == nums[j]:
count = count + 1
if count > max_count:
max_count = count
element = i
if max_count > size // 2:
return nums[element]```

Test Case Analysis: Let’s check if this code works properly by execution it on our examples/test-cases:

It passed all the test cases.?

Complexity Analysis

• Time Complexity: Since the list had to be travelled repeatedly for every element, hence a nested `for` loop was required in this method. Thus, this leads to quadratic runtime complexity of O(n2).
• Space Complexity: No extra space is required in this method. Hence, it has a space complexity of O(1).

Discussion

Although this method works properly, it is not the most efficient solution. In this approach, we are repeatedly traversing the entire list for each element in the given list. This accounts for a quadratic runtime complexity. But do we need to traverse the entire list repeatedly for each element again and again?

The answer to the above question is that there are better ways that allow us to reach a more efficient solution with a better runtime complexity. The next solution discusses an approach that will yield you the output in linear time.

## ?️Method 2: Using A Python Dictionary

Approach: The idea here is to create a dictionary that will store the count of each number, thereby avoiding the need to traverse the list, again and again, leading to linear time complexity. Traverse the list and store the element and its count within the dictionary. If the element is already present in the dictionary, you just have to increment its count and update it in the dictionary. This helps you to avoid iterating over the list for the same element again.

Algorithm:

1. Initialize the dictionary and a count variable.
2. Traverse the `nums` and if the element is not present in the dictionary, add the element to it. Otherwise, update the count of the element.
3. Return the element if its count becomes more than `n//2`.

Let’s have a look at the following illustration to have a deeper understanding of this concept.

Let’s look at the code:

```def majority_ele(nums):
d = {}
count = 1
for i in nums:
if i not in d:
d[i] = count
else:
d[i] += count
val = max(d, key=d.get)
if d[i] >= (len(nums) // 2):
return val```

Test Case Analysis: Let’s run this code on our examples to verify if it works.

Yeah! It passed all the test cases.

Complexity Analysis

• Time Complexity: In this method, we traverse the `nums` list only once. Hence, it has a time complexity of O(n).
• Space Complexity: An extra space is required in this method for storing the elements in the dictionary. Hence, it has a space complexity of O(n).

Discussion

Though this approach was more efficient in terms of time complexity, we used an extra space here. This led to a linear time complexity as opposed to the brute-force method which had a constant space complexity. Thus, can we optimize the solution to work in linear time with constant space complexity, i.e., O(1)?

## ?️Optimized Solution: Boyer–Moore Majority Vote Algorithm

If it is confirmed that the majority element exists in the list then Boyer-Moore Majority Vote Algorithm is a very effective and probably the easiest way to find the majority element in the given list. Since the majority element occurs more than `n//2` times, its recurrence is greater than any remaining elements combined. The idea behind this algorithm is that for the occurrence of a majority element, we can ignore the non-majority elements.

Algorithm:

1. Initialize a variable “`major`” that will store the majority element to `-1` and count to `0`
2. Traverse the `nums` list. If the count is `0`, update the current element as the majority element and initialize the count to `1`.
3. If the majority element is equal to the current element, increase the count variable. Else, decrease the count variable.
4. Return the majority element.

➠ The following illustration will help you to understand the approach used in this method.

Let’s look at the code to implement the approach explained above:

```def majority_ele(nums):
major = -1
count = 0
for i in range(len(nums)):
if count == 0:
major = nums[i]
count = 1
elif major == nums[i]:
count = count + 1
else:
count = count - 1
return major```

Test Case Analysis: Let’s run this on our examples.

Hurray! It works. ?

?Note: The Boyer–Moore majority vote algorithm only works correctly if and only if it is confirmed that the majority element exists.

Complexity Analysis

• Time Complexity: Similar to the second approach where we used a Python dictionary, in this approach too we have to traverse the `nums` list only once. Hence, it has a time complexity of O(n).
• Space Complexity: As no extra space is required in this method, it has a space complexity of O(1).

## Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

✍️ Post Credits: Rashi Agarwal and Shubham Sayon