169. Majority Element

Posted on | In

Bit Manipulation

Question

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

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

My Answer

HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxNum = nums[0];
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i, map.get(i)+1);
                if(map.get(i)>nums.length/2)
                    maxNum = i;
            }
            else{
                map.put(i,1);
            }
        }
        return maxNum;
    }
}

Running time: O(n), 48ms

Space: O(2/n)

Better Answer

Boyer-Moore Voting Algorithm

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

Running time: O(n)

Space: O(1)

Divide and Conquer

Intuition

If we know the majority element in the left and right halves of an array, we can determine which is the global majority element in linear time.

Algorithm

Here, we apply a classical divide & conquer approach that recurses on the left and right halves of an array until an answer can be trivially achieved for a length-1 array. Note that because actually passing copies of subarrays costs time and space, we instead pass lo and hi indices that describe the relevant slice of the overall array. In this case, the majority element for a length-1 slice is trivially its only element, so the recursion stops there. If the current slice is longer than length-1, we must combine the answers for the slice’s left and right halves. If they agree on the majority element, then the majority element for the overall slice is obviously the same1. If they disagree, only one of them can be “right”, so we need to count the occurrences of the left and right majority elements to determine which subslice’s answer is globally correct. The overall answer for the array is thus the majority element between indices 0 and nn.

Complexity Analysis

  • Time complexity : O(nlog)

  • Space complexity :O(logn)

    ​