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

Advertisement

Citation

Click to select citation style

Shovon, A. R. (2021, August 24). Get the majority element from a given list. Ahmedur Rahman Shovon. Retrieved June 22, 2024, from https://arshovon.com/blog/majority-element/

Shovon, Ahmedur Rahman. “Get the majority element from a given list.” Ahmedur Rahman Shovon, 24 Aug. 2021. Web. 22 Jun. 2024. https://arshovon.com/blog/majority-element/.

@misc{ shovon_2021,
    author = "Shovon, Ahmedur Rahman",
    title = "Get the majority element from a given list",
    year = "2021",
    url = "https://arshovon.com/blog/majority-element/",
    note = "[Online; accessed 22-June-2024]"
}
Get the majority element from a given list
Previous post

Merge Sort