Majority Element

Given an integer slice nums, return the element that appears more than n/2 times. You may assume such an element always exists.

A counting map works but uses extra memory. There is a linear-time, constant-space solution using the Boyer-Moore voting invariant.

Why this is worth learning

Boyer-Moore stores a cancellation balance, not the candidate's actual frequency. The majority-exists precondition is what lets cancellation identify an answer without a verification pass.

Before coding: one-minute experiment

For [2,1,2,3,2,2,4], what candidate survives, and is the final balance its frequency?

Function signature

func MajorityElement(nums []int) int

Inputs / outputs

• nums: non-empty slice of integers.
• Return: the value that appears more than len(nums)/2 times.

Example

nums = [2,2,1,1,1,2,2]
Output: 2

Reasoning: The majority element must survive pair-cancellation.

Constraints

• 1 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000
• A majority element always exists.

Core idea (near-solution)

Boyer-Moore voting pairs off different values and cancels them.

Maintain:

• candidate: the current majority candidate
• count: the candidate's net "advantage"

Invariant: the processed prefix can be partitioned into unequal pairs that cancel and exactly count unmatched copies of candidate. The balance is nonnegative; when it is zero there is no unmatched candidate. It is not the candidate's frequency or its global prefix advantage, because earlier pairs may contain two values different from the current candidate.

Algorithm (step-by-step)

1. Initialize count = 0.
2. For each value x in nums:
   • If count == 0, set candidate = x.
   • If x == candidate, increment count; otherwise decrement count.
3. Return candidate.

Correctness sketch

View a decrement as removing a pair of unequal values from the processed input. Removing such a pair cannot eliminate the strict majority: if the pair contains it, both its count and the non-majority count fall by one; otherwise only non-majority values are removed. A positive balance represents unmatched copies of the current candidate. When the balance is zero, the next value can start a new unmatched group. At the end, a strict majority must survive all possible unequal cancellations, so the remaining candidate is that majority.

Trace (hand walkthrough)

Example input:
nums = [2,2,1,1,1,2,2]
Output: 2

Reasoning: The majority element must survive pair-cancellation.

Walk:
- candidate=2, count=1 (after first 2)
- next 2 -> count=2; next 1 -> count=1; next 1 -> count=0
- index 4 is 1: count was 0, so candidate=1, count=1
- index 5 is 2: cancel the unmatched 1, so count=0
- index 6 is 2: choose candidate=2, count=1
- all seven values are consumed; return 2 (four occurrences, balance only 1)

Pitfalls to avoid

• Using this algorithm when no majority is guaranteed (it can return a non-majority then).
• Forgetting to reset the candidate when count hits zero.

Debugging lens

Do not add tests demanding a meaningful answer when no majority exists without changing the contract. For the promised domain, shuffle majority and minority values to force several candidate resets.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• The problem guarantees a majority, so no second verification pass is required.

Reconstruction checkpoint

For [2,1,2,3,2,2,4], what candidate survives, and is the final balance its frequency?

Return to Array & String · Module quiz