Find All Elements Appearing More Than a Third of the Time

Given an array nums, return all elements that appear MORE THAN ⌊n/3⌋ times. It's mathematically impossible for three different values to each exceed a third of the array, so the answer never has more than 2 elements — it may have 0, 1, or 2. Counting occurrences of every value from scratch works, but it repeats the same scan for every duplicate of a non-qualifying value. The Boyer-Moore voting technique, extended to track two candidates instead of one, finds both possible answers in a single pass — followed by a quick second pass to confirm each one actually clears the bar.

Test Case 1:

Input:nums = [1, 1, 1, 3, 3, 2, 2, 2]

Output:[1, 2]

Explanation:1 and 2 each appear 3 times out of 8 (> ⌊8/3⌋ = 2). 3 appears only twice, so it doesn't qualify.

Test Case 2:

Input:nums = [3, 2, 3]

Output:[3]

Explanation:3 appears twice out of 3 elements (> ⌊3/3⌋ = 1). 2 appears only once.

Test Case 3:

Input:nums = [1, 2, 3, 4]

Output:[]

Explanation:Every value appears exactly once — none exceeds ⌊4/3⌋ = 1.

Constraints

◆1 ≤ nums.length ≤ 5×10⁴
◆-10⁹ ≤ nums[i] ≤ 10⁹

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 4-9 integers, -10 to 10

1	class Solution {
2	public int[] majorityElementII(int[] nums) {
3	int cand1 = 0, cand2 = 1, count1 = 0, count2 = 0;
4	for (int num : nums) {
5	if (num == cand1) {
6	count1++;
7	} else if (num == cand2) {
8	count2++;
9	} else if (count1 == 0) {
10	cand1 = num;
11	count1 = 1;
12	} else if (count2 == 0) {
13	cand2 = num;
14	count2 = 1;
15	} else {
16	count1--;
17	count2--;
18	}
19	}
20	count1 = 0;
21	count2 = 0;
22	for (int num : nums) {
23	if (num == cand1) count1++;
24	else if (num == cand2) count2++;
25	}
26	List<Integer> result = new ArrayList<>();
27	if (count1 > nums.length / 3) result.add(cand1);
28	if (count2 > nums.length / 3) result.add(cand2);
29	int[] arr = new int[result.size()];
30	for (int i = 0; i < arr.length; i++) arr[i] = result.get(i);
31	return arr;
32	}
33	}
34

1

3

2

0

1

2

3

4

5

6

7

Variables

cand10

cand21

count10

count20

INITIALIZE

Track two candidates and two counts, both starting at 0. Walk through nums once, voting.

Step 1 / 14

Approach & Solutions

Brute Force

Brute

For each value in the array (skipping ones already added to the result), count its total occurrences with a nested scan and keep it if that count exceeds ⌊n/3⌋. Correct, but every value that DOESN'T qualify gets re-scanned from scratch on every one of its repeated occurrences.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int[] majorityElementII(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (result.contains(nums[i])) continue;
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i]) count++;
            }
            if (count > nums.length / 3) result.add(nums[i]);
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < arr.length; i++) arr[i] = result.get(i);
        return arr;
    }
}

Optimal — Extended Boyer-Moore Voting

Optimal

Since it's mathematically impossible for three different values to each exceed a third of the array, at most 2 values can ever qualify. Track two candidates and two counts through a single voting pass (the standard Boyer-Moore trick, extended to two slots), then verify with a second pass — surviving the vote only narrows the field to the two values that COULD be majorities, it doesn't guarantee either one actually is.

TimeO(n)