Problem Explanation

This problem requires us to find all elements in an array that appear more than ⌊ n/3 ⌋ times where n is the size of the array. The algorithm should run in O(n) time and use O(1) space.

For Example:

If the input is [3,2,3], the output will be [3] because 3 appears more than 3/3 = 1 time.

If the input is [1,1,1,3,3,2,2,2], the 1 and 2 appear more than 8/3 ≈ 2 times, hence the result will be [1,2].

Approach

This problem can be solved using the Boyer-Moore Majority Vote algorithm. This algorithm is used to find the majority of a sequence of elements. It works by keeping a counter for a potential majority element, and resetting it to a new element whenever the counter reaches zero. In this problem, we need to find all elements that appear more than n/3 times, so we will need to keep track of two potential candidates.

The first step is to find the two candidates. We start by initializing two candidates with different values and two counters. Then, for each number in the array, if it equals either candidate we increment the corresponding counter. If both counters are not zero, we decrement both counters. The two numbers left after this process are the majority candidates.

Finally we check if the two candidates actually have more than n/3 occurrences in the array. This is done by simply looping through the array again and comparing each element to the two candidates.

Let's step through an example.

Example

Let's consider the example [1,1,1,3,3,2,2,2]

1
2
3Candidate1 = 1, Candidate2 = 3
4Count1 = 3, Count2 = 3 

The function will return [1, 2], because 1 and 2 appear more than ⌊ 8/3 ⌋ times.

Solution

Python

1
2python
3class Solution:
4    def majorityElement(self, nums):
5        if not nums: return []
6        count1, count2, candidate1, candidate2 = 0,0,0,1
7        for num in nums:
8            if num == candidate1:
9                count1 += 1
10            elif num == candidate2:
11                count2 += 1
12            elif count1==0:
13                candidate1, count1 = num, 1
14            elif count2 == 0:
15                candidate2, count2 = num, 1
16            else:
17                count1, count2 = count1 - 1, count2 - 1
18
19        return [num for num in (candidate1, candidate2) 
20                if nums.count(num) > len(nums) // 3]

Java

1
2java
3class Solution {
4  public List<Integer> majorityElement(int[] nums) {
5    Integer candidate1 = null, candidate2 = null;
6    int count1 = 0, count2 = 0;
7
8    for (int num : nums) {
9      if (num == candidate1) count1++;
10      else if (num == candidate2) count2++;
11      else if (count1 == 0) { candidate1 = num; count1++;}
12      else if (count2 == 0) { candidate2 = num; count2++;}
13      else { count1--; count2--;}
14    }
15
16    count1 = count2 = 0;
17    for (int num : nums) {
18      if (num == candidate1) count1++;
19      else if (num == candidate2) count2++;
20    }
21
22    List<Integer> res = new ArrayList<>();
23    if (count1 > nums.length/3) res.add(candidate1);
24    if (count2 > nums.length/3) res.add(candidate2);
25    return res;
26  }
27}

JavaScript

1
2javascript
3var majorityElement = function(nums) {
4    if (nums.length === 0) return [];
5    
6    let count1 = 0, count2 = 0, candidate1 = 0, candidate2 = 1;
7    
8    for (let num of nums) {
9        if (num === candidate1) count1++;
10        else if (num === candidate2) count2++;
11        else if (count1 === 0) {
12            candidate1 = num;
13            count1++;
14        }
15        else if (count2 === 0) {
16            candidate2 = num;
17            count2++;
18        }
19        else {
20            count1--;
21            count2--;
22        }
23    }
24    
25    count1 = 0;
26    count2 = 0;
27    
28    for (let num of nums) {
29        if (num === candidate1) count1++;
30        else if (num === candidate2) count2++;
31    }
32    
33    let result = [];
34    
35    if (count1 > nums.length / 3) result.push(candidate1);
36    if (count2 > nums.length / 3) result.push(candidate2);
37    
38    return result;
39};

In the JavaScript implementation, we follow the same approach as in the other languages. We first set up two different candidates as potential majority elements and begin to traverse the array. If we encounter a number that is equal to either of the candidates, we increment the respective counter. If both counters are nonzero and the number is new, we decrement both counters. If the counter for a candidate drops to zero, we change the candidate to the new number and increment its counter. By the end of the pass through the array, we should have up to two candidate numbers. For the candidates to be valid, they must appear more than n/3 times in the array, thus we make another pass to count their occurrences. If a candidate's count satisfies this condition, we add it to the result list.