Understanding the Problem

This is a generalization of the classic Majority Element problem (LeetCode 169), where we needed to find the element appearing more than n/2 times. That problem guaranteed exactly one answer. Here, we need to find all elements appearing more than n/3 times.

The first thing to notice is a mathematical constraint: there can be at most two elements that appear more than n/3 times. Think about it. If three elements each appeared more than n/3 times, that would account for more than n total elements, which is impossible. So our answer list has at most 2 elements.

This observation is the foundation for every approach. The brute force counts every element, the hash map approach does it efficiently, and the optimal Boyer-Moore approach exploits this "at most 2 candidates" fact to use constant space.

Key Constraints:

1 <= nums.length <= 5 * 10^4 → With n up to 50,000, O(n^2) means 2.5 billion operations, which is too slow. We need O(n log n) or better.
-10^9 <= nums[i] <= 10^9 → Values span the full 32-bit integer range, so we can't use array indexing for counting. We need a hash map or a comparison-based approach.
The follow-up explicitly asks for O(n) time and O(1) space, hinting at the Boyer-Moore Voting algorithm.

Approach 1: Hash Map Counting

Intuition

The most natural approach: count how many times each element appears, then check which counts exceed n/3. A hash map gives us O(1) lookups and insertions, so we can count everything in a single pass and then filter.

This is the approach most people would reach for in a real codebase. It's clean, readable, and hard to get wrong.

Algorithm

Create a hash map to store the count of each element.
Iterate through nums, incrementing the count for each element.
Calculate the threshold as n / 3.
Iterate through the hash map entries, collecting elements whose count exceeds the threshold.
Return the result list.

Example Walkthrough

1Initialize: scan nums to count each element

1/6

Code

Complexity Analysis

Time Complexity: O(n). We iterate through the array once to build the count map, and once more through the map entries. Both passes are O(n).
Space Complexity: O(n). In the worst case (all unique elements), the hash map stores n entries.

This approach works correctly but uses O(n) extra space. Since at most 2 elements can be the answer, can we find those candidates without storing counts for every element?

Approach 2: Sorting

Intuition

If we sort the array, all occurrences of the same element will be adjacent. An element that appears more than n/3 times will occupy a contiguous block of length greater than n/3. So after sorting, we can scan the array and check whether each element's run length exceeds the threshold.

This approach trades the O(n) space of a hash map for the O(n log n) time of sorting. It's a reasonable middle ground if you want constant auxiliary space and can afford the slower runtime.

Algorithm

Sort the array.
Initialize a counter and iterate through the sorted array.
For each new value, count its consecutive occurrences.
If the count exceeds n/3, add it to the result.
Return the result.

Example Walkthrough

1Before sorting: nums = [3, 2, 3, 1, 2, 3, 2]

1/6

Code

Complexity Analysis

Time Complexity: O(n log n). Sorting takes O(n log n). The subsequent linear scan is O(n), so sorting dominates.
Space Complexity: O(1). We use only a few variables. Some sorting algorithms use O(log n) stack space, but no auxiliary data structures.

Sorting works but takes O(n log n) and modifies the input. Since at most 2 elements can be the answer, can we find those candidates in a single pass without sorting or extra space?

Approach 3: Boyer-Moore Voting (Optimal)

Intuition

This is the extended version of the Boyer-Moore Majority Vote algorithm. The original algorithm finds the element appearing more than n/2 times using one candidate and one counter. For n/3, we extend it to two candidates and two counters.

The core idea is a cancellation mechanism. If three people all vote for different candidates, their votes cancel out. After all cancellations, whoever remains standing must be a potential majority candidate. But "potential" is the key word. We still need a second pass to verify.

Why does this work?

If an element truly appears more than n/3 times, its count can be decremented at most (n - count) / 2 times (since each cancellation requires two other distinct elements). Since count > n/3, the number of cancellations is at most (n - n/3) / 2 = n/3, which is less than the element's count. So it will survive the first pass.

But the converse isn't true. An element can survive without being a majority element. That's why the second verification pass is mandatory.

Algorithm

Initialize two candidates (cand1, cand2) and their counts (count1 = 0, count2 = 0).
First pass (find candidates): iterate through nums:

If num == cand1, increment count1.
Else if num == cand2, increment count2.
Else if count1 == 0, set cand1 = num and count1 = 1.
Else if count2 == 0, set cand2 = num and count2 = 1.
Else decrement both count1 and count2.

Second pass (verify candidates): count the actual occurrences of cand1 and cand2.
Add to result any candidate whose count exceeds n/3.

Example Walkthrough

1Initialize: cand1=?, count1=0, cand2=?, count2=0

1/7

Code

Complexity Analysis

Time Complexity: O(n). Two passes through the array, each O(n). Total is O(2n) = O(n).
Space Complexity: O(1). Only uses a fixed number of variables: two candidates, two counters, and the result list.

Majority Element II

Understanding the Problem

Key Constraints:

Approach 1: Hash Map Counting

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Sorting

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Boyer-Moore Voting (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium