Skip to content

169. Majority Element

Array Hash Table Divide and Conquer Counting

🔗 Source

Intuition

Given an list of numbers of size n, return the element that appears more than ⌊n / 2⌋ times.

  • You may assume that the majority element always exists in the array.
  • There is only one majority element in the given array.
  • An array of Integer
  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Solution 1 HashMap

Approach

  • Step 1: Create a hash map res to store the stats of elements in the given array
  • Step 2: During the loop iteration, for nums[i]
    • If res does not contain a key nums[i], add it and set its value as the number of appearance, initializing as 1.
    • If res contains a key nums[i], update its number of appearance.
  • Step 3: When we encounter a key whose value is greater than ⌊n / 2⌋, return this key.

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(k)\) for k distinct element in array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            int before = map.getOrDefault(nums[i], 0);
            if (before == n / 2) {
                return nums[i];
            }
            map.put(nums[i], before + 1);
        }
        return -1;
    }
}

Solution 2 "Vote"

Approach

There is a "clever" approach to solve this problem,

  • Firstly, we set nums[0] as candidate res, and initialize the candidate's vote count to 1.
  • When we encounter the same number as res is , the vote count++, otherwise the vote count--.
  • When the vote count is 0, change the candidate and reset the vote count to 1.
  • After traversing the array, our candidate number res is the final answer.

Why? This is equivalent to each ‘majority element’ canceling out with other elements in pairs. By the end, there will definitely be at least one ‘majority element’ remaining.

For this solution, as we simply traverse the array without implementing any other extra data structure, we optimize the space complexity!

Reference: 🔗 Boyer-Moore Majority Vote Algorithm

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int res = 0;
        for (int num : nums) {
            if (count == 0) {
                res = num;
            }
            if (num == res) {
                count++;
            } else {
                count--;
            }
        }
        return res;
    }
}