Majority Element Solution

Problem

Given an integer array, find the element that appears more than half the time. The problem guarantees that such an element always exists.

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: 2 appears 4 times in an array of 7 elements, and 4 > 7/2 = 3.5.

A single-element array like [6] is also valid — the lone element trivially satisfies the majority condition.

Intuition

Because the majority element appears more than n/2 times, it outnumbers all other elements combined. Imagine each majority vote cancelling one opposing vote: even after every other element has cancelled as many majority votes as possible, the majority element still has leftover votes. That surplus is the key insight behind the Boyer-Moore Voting Algorithm — one pass, no extra memory.

Approach 1 — Hash Map

Count each element's frequency, then return whichever element first exceeds n/2.

Compute the majority threshold: n // 2.
Walk through the array, incrementing each element's count in a hash map.
As soon as any count exceeds the threshold, return that element immediately.

1def majorityElement(nums):
2    counts = {}
3    threshold = len(nums) // 2
4    for num in nums:
5        counts[num] = counts.get(num, 0) + 1
6        if counts[num] > threshold:  # early return — no need to finish the array
7            return num

Time: O(n) — one pass through the array.
Space: O(n) — the hash map stores at most n distinct elements.

Approach 2 — Boyer-Moore Voting

Maintain a single candidate and a running vote count. When votes cancel to zero, adopt the next element as the new candidate.

Start with candidate = None and count = 0.
For each number: if count == 0, make this number the new candidate.
If the current number matches the candidate, increment count; otherwise decrement it.
Return the candidate — the majority element's surplus votes can never be fully cancelled out.

1def majorityElement(nums):
2    candidate = None
3    count = 0
4    for num in nums:
5        if count == 0:
6            candidate = num  # adopt a new candidate whenever all prior votes cancel out
7        count += 1 if num == candidate else -1
8    return candidate

Time: O(n) — single pass through the array.
Space: O(1) — only two variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Hash Map	O(n)	O(n)	When clarity matters more than memory, or you need to extend to multiple majority elements
Boyer-Moore Voting	O(n)	O(1)	When memory is constrained or the interviewer explicitly asks for constant extra space

Common Mistakes

Using >= threshold instead of > threshold — the threshold is n // 2 (integer division), so you need strictly greater than. For n=6, threshold=3, meaning an element needs at least 4 appearances — checking >= 3 would wrongly accept an element with only 3 occurrences.
Updating the candidate after adjusting the count — in Boyer-Moore, the candidate check (if count == 0) must come before the vote adjustment. Swapping the order means the new candidate immediately loses a vote against itself, breaking the invariant.
Adding a second verification pass — Boyer-Moore only needs verification when a majority element is not guaranteed. Here the problem guarantees one exists, so the survivor of the voting pass is always correct; a second counting pass is wasted work.
Wrong index in the sort shortcut — sorted(nums)[len(nums) // 2] is a valid O(n log n) approach since the majority element must land at the median. A common off-by-one is using [len(nums) // 2 - 1], which can miss the majority element for even-length arrays.
Assuming candidate = 0 in Java/C++ might be returned — initializing candidate to 0 is harmless because count also starts at 0, so the very first element unconditionally becomes the candidate. The initial value of candidate is never observable.

Majority Element — Solution