Reference: LeetCode
Difficulty: Medium

Problem

Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ times.

Note: The algorithm should run in linear time and in $O(1)$ space.

Example: 

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

Analysis

Methods:

  1. HashMap
    Time: $O(N)$
    Space: $O(N)$

  2. Boyer-Moore Majority Vote Algorithm

Reference: My Understanding of Boyer-Moore Majority Vote

Let’s first go back to 169. Majority Element and try to think about the idea of pairing, which happens when count -= 1.

Suppose we have 9 items in an array:

No matter in what order we select elements from the array, we can only get two results: Fully Paired and Partially Paired.

1
2
3
4
5
6
7
8
9
10
11
12
public int majorityElement(int[] nums) {
  int count = 0;
  Integer candidate = null;
  for (int val : nums) {
    if (count = 0) {
      candidate = val;
    }
    count += (val == candidate) ? +1 : -1;
  }
  // possible verification
  return count;
}

So here comes the n/3 problem, we would only think about the fully pairing situation. If the over one third majority exists, it should be left after pairing.

And why would we use three elements as a pair? Because it makes sure that in fully pairing the count of the majority element equals n/3.

More Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// [ 1  1  1  3  3  2  2  2 ]
//   
//    1 (3)     
//    1 (2)     3 (2)    2 (2)  => now count1 = 1 and count2 = 0
//    1 (1)     3 (1)    2 (1)  => when the last 2 comes in, candidate2 will be updated to 2
//   count1    count2    other


// [ 1  2  3  4  5  5  5  5  5 ]
// 
//    1 (1)     2 (1)    3 (1)   => both count1, count2 drop to 0
//   count1    count2    other

//              5 (5)
//              5 (4)
//              5 (3)
//              5 (2)
//    4 (1)     5 (1)            => we need to check if 4 and 5 are valid candidates.
//   count1    count2    other

Note:

  • The ordering of if is very important. Though there are many branches, but each time only one could be executed.
  • It is okay to initialize candidates with arbitrary numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public List<Integer> majorityElement(int[] nums) {
  int n = nums.length;
  List<Integer> result = new ArrayList<>();
  int candidate1 = 0, candidate2 = 0;
  int count1 = 0, count2 = 0;
  
  // First Pass
  for (int val : nums) {
    if (val == candidate1) {
      count1 += 1;
    } else if (val == candidate2) {
      count2 += 1;
    } else if (count1 == 0) { // update candidate
      candidate1 = val;
      count1 += 1;
    } else if (count2 == 0) { // update candidate
      candidate2 = val;
      count2 += 1;
    } else {
      count1 -= 1;    // pairing
      count2 -= 1;    // pairing
    }
  }
  
  // Second Pass - Validity Checking
  count1 = 0;
  count2 = 0;
  for (int val : nums) {
    if (val == candidate1) {
      count1 += 1;
    } else if (val == candidate2) {
      count2 += 1;
    }
  }
  if (count1 > n / 3) result.add(candidate1);
  if (count2 > n / 3) result.add(candidate2);
  return result;
}

Time: $O(N)$
Space: $O(1)$