Majority Element II
The key idea
At most two values can each appear more than
⌊n/3⌋ times (three such values would already exceed n). So you only ever need to track two candidates. Boyer-Moore voting generalizes: keep two candidates with two counts; an element that matches a candidate bumps its count, an element matching neither — when both counts are already zero — becomes a new candidate; otherwise it cancels one vote from each. A final counting pass confirms the survivors really cross the threshold.Problem
Given an integer array nums of size n, return all the elements that appear more than ⌊ n/3 ⌋ times.
The answer may be returned in any order. Note that ⌊ x ⌋ denotes the floor function — the largest integer not greater than x.
Constraints
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9- *Follow-up:** Could you solve the problem in linear time and in
O(1)space?
Examples
Input: nums = [3,2,3]
Output: [3]
Input: nums = [1]
Output: [1]
Input: nums = [1,1,1,3,3,2,2,2]
Output: [1,2]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY