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)$

  1. 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)$


Comment