229. Majority Element II
On This Page
Given an integer array of size
n, find all elements that appear more than ⌊ n/3 ⌋ times.
The immediate solution would involve using a hashmap or dictionary to track the occurrence of each number in the array. After which, we can iterate over the dictionary to find numbers whose occurrences are greater than
Hints & Tips
- There can be at most one or two majority elements which appear more than
n/3times in the array.
- Employ the Boyer-Moore Voting Algorithm.
We can apply a variation of the Boyer-Moore Voting Algorithm. The fundamental insight behind this algorithm is that at each step, we can discard a certain portion of the elements and still have the same majority elements.
For this problem, we’ll maintain two counters and two majority candidates. This is because there could be at most two majority elements.
- Initialize two counters and two majority candidates.
- Parse the array:
- If the current element matches either of the majority candidates, increase the respective counter.
- If both counters are zero, reset both majority candidates and counters.
- Otherwise, decrease both counters.
- Reassess the majority candidates by verifying their counts.
def majorityElement(self, nums: List[int]) -> List[int]: cand1 = 0 # Two majority candidates and their counters cand2 = 1 count1 = 0 count2 = 0 for num in nums: if num == cand1: count1 += 1 elif num == cand2: count2 += 1 elif count1 == 0: cand1, count1 = num, 1 elif count2 == 0: cand2, count2 = num, 1 else: count1, count2 = count1 - 1, count2 - 1 res =  count = len(nums) // 3 for cand in (cand1, cand2): if nums.count(cand) > count: res.append(cand) return res