Majority Element

EASY✓ CHIP-TIMEDLC #169 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

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

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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED