Majority Element

EASY✓ CHIP-TIMEDLC #169 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: One value holds more than half the seats in the array — find it. Sorting works, a counting table works, but the strict-majority property is strong enough to finish in one pass with a single counter and no memory at all.

An array of integers arrives carrying one value that dominates it — occupying strictly more than half of all the positions — and the task is to name that value.

No ties are possible under this rule: because the winning value holds more than half, at most one value can ever qualify, so the answer is always a single number.

A majority value is guaranteed to exist in every input handed over on this course — the only real work is finding it efficiently, not confirming that one exists.

arrays hold at least one element
a strict majority value is guaranteed to exist in every input
values may be negative, zero, or positive
exactly one value can ever qualify, so the answer is unambiguous

EX 01

nums = [7]

→ 7

a field of one

EX 02

nums = [3, 3, 2]

→ 3

smallest real contest

EX 03

nums = [2, 2, 1, 1, 2]

→ 2

majority splits around the middle

The hintstake only what you need

HINT 1 THE NUDGE

Counting every value's occurrences answers it, but a strict majority is stronger than merely most frequent — more than half. What does that surplus let you throw away?

HINT 2 THE STRUCTURE

Strike out one majority vote together with one non-majority vote, and the majority still leads whatever remains. Cancellation can never dethrone it.

HINT 3 ONE STEP FROM THE ANSWER

Boyer–Moore: carry a candidate and a counter. Matching value +1, different value −1, counter at zero → adopt the current value as the new candidate. Whoever survives the pass is the majority.

Coach's boardthe pattern, step by step

THE VOTE THAT CAN'T LOSEPATTERN · BOYER–MOORE VOTEnums = [2, 2, 1, 1, 2]

CANDIDATE / COUNT

candidate → —

count → 0

STEP 1

Boyer-Moore vote: carry one candidate and a counter through the whole array.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/majority-element.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = nums[0]
        count = 0
        for x in nums:
            if count == 0:      # previous candidate fully cancelled out
                candidate = x
            count += 1 if x == candidate else -1
        return candidate

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 9 LN

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        for x in nums:
            count = 0
            for y in nums:  # re-count x from scratch
                if y == x:
                    count += 1
            if count > n // 2:
                return x
        return -1  # unreachable: a majority always exists

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x; // previous candidate cancelled out
            count += (x == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        for (int x : nums) {
            int count = 0;
            for (int y : nums) { // re-count x from scratch
                if (y == x) count++;
            }
            if (count > n / 2) return x;
        }
        return -1; // unreachable: a majority always exists
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED