Majority Element
- 2 min read
- Array
- LC-Easy
3 years ago
Solution
- The trivial solution is easy- use a hashmap and then a variable to keep track of the maximum frequency.
- Use Boyer-Moore Algorithm
- Initialize count to 0. Keep track of number that we're keeping count of
- If the number is seen, increment count
- If any other number is seen, decrement count.
- If we're about to decrement and then current count is 0, it means that the there are atleast that many non-needed elements (equal in number to the needed elements)
- The above sentence is confusing as fuck, but use this example input: [2, 2, 1, 1, 1, 2, 2]
- Assume we're on the 3 ones in the middle. Our count would be 2 at the end of the second 2.
- At the first 1, count decrements by 1.
- At the second 1, count decrements by 1. Currently count is 0
- At the third 1, count is 0. If we decrement it'll become negative. At this point, we've seen as many 1s and we've seen 2s. And 2 is the majority element. So we can consider these elements as not part of the array, if that makes sense. We don't need to consider them because they're at equal counts. There's going to be one element that's extra, and that value will be tracked when we get to the end of the array.
- Remember, this solution only works if we're guaranteed that the majority element exists in the array.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def majorityElement(self, nums: List[int]) -> int:
count = 1
ans = nums[0]
for i in range(1, len(nums)):
if nums[i] == ans:
count += 1
else:
if count == 0:
ans = nums[i]
count += 1
else:
count -= 1
return ans