Majority Element

---

Majority Element: Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

---

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

---

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

---

Try this Problem on your own or check similar problems:

1. Most Frequent Even Element
2. Majority Element II

Solution:

Java

public int majorityElement(int[] nums) {
    int count = 0, bestCandidate = nums[0], i = 0;
    while(i < nums.length){
        if(count == 0){
            bestCandidate = nums[i];
        }
        if(nums[i] == bestCandidate){
            ++count;
        }
        else{
            --count;
        }

        ++i;
    }
    return bestCandidate;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let count = 0;
  let bestCandidate = nums[0];
  let i = 0;

  while (i < nums.length) {
    if (count === 0) {
      bestCandidate = nums[i];
    }
    if (nums[i] === bestCandidate) {
      count++;
    } else {
      count--;
    }
    i++;
  }

  return bestCandidate;
};

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        bestCandidate = nums[0]
        i = 0

        while i < len(nums):
            if count == 0:
                bestCandidate = nums[i]
            if nums[i] == bestCandidate:
                count += 1
            else:
                count -= 1
            i += 1

        return bestCandidate

C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int bestCandidate = nums[0];
        int i = 0;

        while (i < nums.size()) {
            if (count == 0) {
                bestCandidate = nums[i];
            }
            if (nums[i] == bestCandidate) {
                count++;
            } else {
                count--;
            }
            i++;
        }

        return bestCandidate;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We could use hashmap, iterate over input array elements and keep count of each of element's frequency. At the end we would return the element with the highest count (value in hashmpa). This of course leads to linear space complexity and follow up would be to do it without auxiliary/helper data structure. To solve this in constant space we utilize Boyer-Moore Voting Algorithm (if you didn't know about it and wondering how can someone come up with this during the interview, the answer is that it rarely occurs if people haven't already practiced similar problem). It's a simple algorithm that resembles the real voting process with a twist. We iterate over array and keep the count variable that basically increments if the current element is the same us our currently chosen bestCandidate, otherwise we decrement the count if the element is different that our bestCandidate. At the beginning of the loop we always check if we need to pick another candidate and discard the voting so far (note that when you turn count = 0, every element we already iterated over doesn't affect the end solution, it's like we're starting anew). Why does this work? Let's check an example

[2, 2, 3, 2, 3, 1 | 3, 2 | 3, 3, 2, 2 | 3, 3, 3, 3]

Note that we use pipe seperation every time we hit count = 0, but also note that every time (except for the last one when we found our majority element) we're discarding the same amount of majority and non-majority elements when we hit count = 0. Since by the problem statement the majority element will be in the array (we can also iterate once more if we don't have this guarantee to check if it really occurs ⌊n / 2⌋ times.), it's safe to discard all of this pipe-seperated groups where we have the same number of majority and non-majority elements until we reach part of the array where the count doesn't go to zero and continues like that until the end of array. In that case we have found our majority element.