Arrays & Hashing · LC #169
Majority Element
Find the element that appears more than n/2 times in an array. The optimal solution is Boyer-Moore Voting - O(n) time, O(1) space - a beautiful algorithm worth memorizing.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given array `nums` of size `n`, return the **majority element** - the element that appears more than `n/2` times. One always exists.
Sample I/O
Input: nums = [3,2,3] Output: 3 Input: nums = [2,2,1,1,1,2,2] Output: 2
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
Because the majority element appears more than half the time, it can "absorb" all opposition. Whenever we pair a majority element with a non-majority element and cancel them, the majority element still has votes left over. The last surviving candidate is always the majority element.
Core Concept
Boyer-Moore Voting: maintain a candidate and a count. When count reaches 0, the current element becomes the new candidate. For each element, increment count if it matches the candidate; otherwise decrement. Because the majority element outnumbers all others combined, it survives every cancellation and remains the final candidate. Time: O(n), Space: O(1).
When to use
Guaranteed-majority problems where you need O(1) space. When asked for the "most dominant" element with a >50% frequency guarantee. Can extend to finding elements appearing >n/3 times with two candidate slots (LC #229).
When NOT to use
When there is no guaranteed majority element - the algorithm returns a candidate but you must verify it. When you need the exact count of the majority element. When finding elements above a lower threshold (< 50%) - use frequency maps.
Key Insights
What to Know Cold
- The O(1) space is the key insight - hash-map frequency counting is straightforward; Boyer-Moore is the expected elegant answer.
- The algorithm assumes a majority element exists; if uncertain, verify the candidate in a second pass.
- Sorting and returning nums[n/2] also works in O(n log n) - worth mentioning as a simpler baseline.
- Boyer-Moore generalises: k candidate slots find all elements appearing > n/(k+1) times.
- Framing as "votes for a candidate with majority wins the election" helps recall the intuition under pressure.
1 example
Worked Examples
Boyer-Moore Voting
nums = [2,2,1,1,1,2,2]. Majority element is 2 (appears 4/7 times).
candidate=2, count tracks net votes. Each non-2 decrements, each 2 increments. 2 accumulates net +1 at the end and survives as the candidate.
candidate, count = None, 0
for n in [2, 2, 1, 1, 1, 2, 2]:
if count == 0:
candidate = n
count += 1 if n == candidate else -1
print(candidate) # 2Boyer-Moore is a canonical O(1)-space trick. Knowing it signals algorithmic depth beyond the obvious hash-map solution - a differentiator in FAANG bar-raiser rounds.