This problem requires detecting all numbers that occur more than one-third of the array size. Start by quickly scanning the array and maintaining potential candidates with counts. Using either a hash map or the Boyer-Moore variation allows constant-time updates while ensuring no valid majority element is missed.
Problem Statement
Given an integer array of length n, return all elements that appear more than ⌊ n/3 ⌋ times. You must consider arrays where multiple elements can exceed this threshold, but no more than two elements can do so simultaneously due to the n/3 limit.
For example, for nums = [3,2,3], the output is [3] because 3 occurs twice in a length-3 array, exceeding ⌊3/3⌋ = 1. For nums = [1,2], the output is [1,2] since both appear once in length 2, each exceeding ⌊2/3⌋ = 0.
Examples
Example 1
Input: nums = [3,2,3]
Output: [3]
Example details omitted.
Example 2
Input: nums = [1]
Output: [1]
Example details omitted.
Example 3
Input: nums = [1,2]
Output: [1,2]
Example details omitted.
Constraints
- 1 <= nums.length <= 5 * 104
- -109 <= nums[i] <= 109
Solution Approach
Hash Map Counting
Scan the array and maintain a hash map to track frequencies. After scanning, iterate through the map and collect keys whose counts exceed n/3. This approach directly applies the array scanning plus hash lookup pattern but uses O(n) space.
Sorting-Based Counting
Sort the array first, then iterate sequentially to count consecutive duplicates. Add any number whose count exceeds n/3 to the result. This uses sorting to simplify counting and handles the n/3 majority logic without extra hash structures.
Boyer-Moore Variant
Maintain up to two candidates with counters since at most two elements can appear more than n/3 times. Scan the array updating candidates and counters; then verify candidates by a second pass. This minimizes space and avoids hash maps, directly reflecting the array scanning plus conditional count pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity ranges from O(n) with hash counting or Boyer-Moore to O(n log n) with sorting. Space complexity is O(n) for hash map or O(1) for the Boyer-Moore variant. Sorting uses O(1) extra if in-place, otherwise O(n).
What Interviewers Usually Probe
- Expect candidates tracking due to n/3 frequency limit.
- Check whether multiple majority elements are possible; signal for Boyer-Moore.
- Sorting may simplify counts but discuss time-space trade-offs.
Common Pitfalls or Variants
Common pitfalls
- Failing to consider that at most two elements can exceed n/3 and assuming more candidates.
- Using hash maps without verifying counts may include false positives.
- Incorrect integer division when computing ⌊ n/3 ⌋ can yield off-by-one errors.
Follow-up variants
- Majority Element I where n/2 threshold simplifies to single candidate selection.
- Find elements appearing more than n/k times for arbitrary k using extended Boyer-Moore.
- Count elements exceeding a dynamic frequency threshold instead of fixed n/3.
How GhostInterview Helps
- Highlights candidate maintenance strategies for array scanning and hash lookup patterns.
- Simulates step-by-step candidate updates and final verification for n/3 constraints.
- Offers quick checks on edge cases like small arrays or multiple valid majority elements.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the easiest way to find all majority elements for the n/3 threshold?
Use the Boyer-Moore variant keeping up to two candidates and verify counts in a second pass; this avoids full hash maps.
Can sorting alone be used to solve Majority Element II?
Yes, sorting groups identical numbers together, allowing sequential counting, though time becomes O(n log n).
Why is the n/3 limit important for candidate selection?
Because no more than two elements can appear more than n/3 times, so only up to two candidates need tracking.
Does Majority Element II allow negative numbers?
Yes, the algorithm treats all integers the same; counts or candidates are independent of value sign.
Which pattern does this problem best illustrate?
It exemplifies the array scanning plus hash lookup pattern, showing trade-offs between O(n) hash counting and O(1) candidate tracking.
Need direct help with Majority Element II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Majority Element II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the majority element in an array, where the element appears more than n/2 times, using efficient algorithms.
Open problem page#347 Top K Frequent ElementsFind the k most frequent elements from an array using efficient algorithms like hashing and sorting.
Open problem page#594 Longest Harmonious SubsequenceFind the length of the longest harmonious subsequence in an integer array using array scanning and hash-based frequency counting techniques.
Open problem page