EasyPro challengePythonJavaScriptTypeScript
Complexity — Majority Element in O(1) Space
AlgorithmsComplexityArraysBoyer-Moore
solve(nums) — nums has a majority element: a value that appears more thann / 2 times. It is guaranteed to exist. Return it.
Three solutions, three complexities — pick the best:
| Approach | Time | Extra space |
|---|---|---|
| Count with a hash map | O(n) | O(n) |
| Sort and take the middle | O(n log n) | O(1) or O(n) |
| Boyer–Moore voting | O(n) | O(1) |
Boyer–Moore keeps a candidate and a count. A matching value adds a vote, a different
one cancels a vote, and when the count hits zero the next value becomes the candidate.
The majority element outnumbers all the others combined, so it survives every cancellation.
Examples
solve([3,2,3]) → 3
solve([2,2,1,1,1,2,2]) → 2
solve([1]) → 1Sample tests
Test #1Majority at both ends
Input: [[3,2,3]]
Output: 3
Test #2Candidate changes mid-way
Input: [[2,2,1,1,1,2,2]]
Output: 2
Test #3Single element
Input: [[1]]
Output: 1