169. Majority Element

169

EasyArrays and HashingBoyer-Moore votingMajority vote cancellation

Majority Element

Given an array nums of size n, return the majority element, the value that appears more than n/2 times. You may assume that a majority element always exists.

Open official problem prompt ↗

In plain English

Identify the value occupying more than half the array using constant extra memory.

Picture it like this

Like an election where every non-majority voter can be paired to knock out one majority voter; because the majority has more than half the votes, at least one of theirs is always left standing.

Example

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Why: 2 appears 4 times out of 7, which is more than 7/2 = 3.5.

Constraints

n == nums.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9A majority element is guaranteed to exist

Pattern lesson

See the pattern, then code

Majority vote cancellation

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. If you cancel each occurrence of the majority element against one occurrence of any other element, the majority still has leftovers, so the last surviving candidate must be it.

New words, made simpleKnow these before the algorithm

Candidate: The value currently believed to be the majority during the scan.
Vote count: A signed tally that rises for matches and falls for mismatches, resetting the candidate at zero.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash map counting

Works but uses linear extra space.

Count every value and return the one whose count exceeds n/2.

Time O(n)Space O(n)

Sort and pick middle

Correct but slower than necessary.

Sort the array; the element at index n/2 must be the majority.

Time O(n log n)Space O(1)

Best choiceBoyer-Moore voting

Optimal in both time and space.

Maintain one candidate and a cancellation counter in a single pass.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing any prefix, the running count equals the number of remaining unmatched copies of the current candidate in that prefix.

Why this is correct

Reasoning

Each decrement pairs one candidate copy with one different element and discards both. Since the majority element appears more than n/2 times, it cannot be fully cancelled by the fewer than n/2 other elements, so it survives as the final candidate.

The algorithm in three movesSay these aloud before coding

1Keep a running candidate and a count starting at 0

cand=2 cnt=2 then 1,1 -> cnt=0

2When count is 0, adopt the current value as the candidate

cand=1 cnt=1 then dips

3Increment count when the value matches the candidate, otherwise decrement

final cand=2

4After one pass the surviving candidate is the majority element

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readx = 2

2 · Askcount is 0?

3 · Update statecand=None cnt=0

4 · ResultAdopt candidate 2, cnt becomes 1.

Key takeaway

Votes for the candidate rise and fall; the majority element ends as the survivor.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Initialize
Zero count means no active candidate yet.
2
Lines 6-7Reset on empty
When the count reaches zero the previous candidate has been fully cancelled, so we start fresh with the current value.
3
Lines 8Vote
One line adjusts the tally up for agreement and down for disagreement.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element array returns that element
All identical values return that value with count growing to n
Majority interleaved with many minorities still survives because it holds > n/2

Common beginner mistakes

Assuming the returned candidate is verified; this version relies on the guarantee that a majority exists and does not double-check
Resetting the count but forgetting to also update the candidate
Using > n//2 integer comparison incorrectly if you switch to a counting approach

Check your understanding

If no majority were guaranteed, what extra step would make the algorithm safe?

Majority Element

Majority Element

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing