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.

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: after processing the first i elements, count equals the number of candidate occurrences minus the number of non-candidate occurrences in that prefix (after cancellations). A true majority cannot be fully canceled, so the final candidate is the answer.

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

• Invariant: after processing the first i elements, count equals the number of candidate occurrences minus the number of non-candidate occurrences in that prefix (after cancellations). A true majority cannot be fully canceled, so the final candidate is the answer.
• Frequency counts reflect the exact multiplicity of each value.
• The decision rule derived from counts is applied once, so no case is missed.
• Therefore the computed result matches the definition of the problem.

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
- count=0 => candidate=1, count=1; next 1 -> count=2
- next 2 -> count=1; next 2 -> count=2 => candidate=2

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.

Complexity

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

Implementation notes (Go)

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