Given an array numbers of size n, return the majority element.

Description

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.

Examples

Example 1:

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

Example 2:

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

Solution

Approach 1 - Hash Table

• We can use a hash table to store the number of occurrences of each number.
• When the number of occurrences for a number is more than ⌊n / 2⌋, return it.
• Time complexity: O(n)
• Space complexity: O(n)

Solution in Java:

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int major = nums[0];
        HashMap<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for(int i: nums) {
            int numberOfOccurrences;
            if(occurrences.get(i) != null) {
                numberOfOccurrences = occurrences.get(i) + 1;
            }
            else {
                numberOfOccurrences = 1;
            }
            occurrences.put(i, numberOfOccurrences);
            if(numberOfOccurrences > n/2) {
                major = i;
                break;
            }
        }
        return major;
    }
}

Solution in C++:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int major = nums[0];
        map<int, int> occurrences;
        for(auto i: nums) {
            if(occurrences.find(i) == occurrences.end()) {
                occurrences[i] = 1;
            }
            else {
                occurrences[i]++;
                if(occurrences[i] > n/2) {
                    major = i;
                    break;
                }
            }
        }
        return major;
    }
};

Solution in Python 3:

from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        occurrences = {}
        major = nums[0]
        for i in nums:
            occurrences[i] = occurrences.get(i, 0) + 1
            if occurrences[i] > len(nums) / 2:
                major = i
                break
        return major

Approach 2: Boyer-Moore Voting Algorithm

• We can use a counter with initial value to 0 and set the first value as major element.
• Iterate through the given values.
• In each iteration, check the value of the counter. If it is 0, sets the current value as major element. Again, if the current value is same to the major element, increase the counter value by one. Otherwise, decrease the counter value by one.
• Time complexity: O(n)
• Space complexity: O(1)

Solution in Java:

class Solution {
    public int majorityElement(int[] nums) {
        int major = nums[0];
        int count = 0;
        for(int i: nums) {
            if(count == 0) {
                major = i;
            }
            if(i == major)
                count++;
            else
                count--;
        }
        return major;
    }
}

Reference

• Leetcode challenge: Majority Element
• Boyer-Moore Voting Algorithm