Majority Element II

MEDIUM✓ CHIP-TIMEDLC #229 — FULL STATEMENT ↗

The drill: Scan a list of numbers and pick out every value that shows up more than a third of the time — there can be at most two such values, and the trick is spotting them without a full frequency table.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and the task is to name every value that occurs more than a third of the time across the whole array.

At most two distinct values can ever clear that bar at once, since three groups each holding more than a third would already overflow the array — the answer is never more than a pair.

It's possible for zero, one, or two values to actually qualify; a value merely surviving a candidate-selection process still has to be confirmed by an honest count before it counts as a real answer.

EX 01

nums = [3, 2, 3]

→ [3]

ONE VALUE CLEARS N/3 = 1

EX 02

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

→ [1, 2]

TWO VALUES TIE FOR THE TWO SEATS

EX 03

nums = [7]

→ [7]

SINGLE ELEMENT — TRIVIALLY OVER N/3 = 0

arrays hold at least one element
values may be negative, zero, or positive, duplicates included
no more than two values can ever exceed the one-third threshold
the result may come back with zero, one, or two values, in any order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At most how many values can each appear more than n/3 times? Think about how many same-sized groups over that threshold could possibly fit inside n total slots.

HINT 2 THE STRUCTURE

Only two elements can ever qualify, so you don't need a full tally of every value — you just need to track two live candidates at once. That's the Boyer-Moore majority vote, run in parallel for two seats.

HINT 3 ONE STEP FROM THE ANSWER

Sweep once holding two candidate/count pairs: a match bumps that candidate's count, an empty seat adopts the current value, otherwise both counts drop by one together. Finish with a second pass over the array to confirm each surviving candidate truly clears n/3 — a candidate can survive the vote without actually being a majority.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO SEATS, ONE VOTEPATTERN · BOYER-MOORE, TWO SEATSnums = [1, 1, 1, 3, 3, 2, 2, 2]

SEAT 1 / SEAT 2

seat1 → — (0)

seat2 → — (0)

STEP 1

8 values; at most two can exceed n/3 ≈ 2.67. Run two Boyer-Moore seats in parallel.

STEP 1 / 11 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/majority-element-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        cand1 = cand2 = None
        cnt1 = cnt2 = 0
        for v in nums:                  # elect and evict, two seats at once
            if cand1 is not None and v == cand1:
                cnt1 += 1
            elif cand2 is not None and v == cand2:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = v, 1
            elif cnt2 == 0:
                cand2, cnt2 = v, 1
            else:
                cnt1 -= 1
                cnt2 -= 1

        result = []
        for c in (cand1, cand2):        # surviving the vote doesn't guarantee majority — verify
            if c is not None and nums.count(c) > len(nums) // 3:
                result.append(c)
        return result

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

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = []
        counted = set()
        for i in range(n):
            if nums[i] in counted:
                continue
            counted.add(nums[i])
            cnt = 0
            for j in range(n):          # re-scan the whole array for this candidate
                if nums[j] == nums[i]:
                    cnt += 1
            if cnt > n // 3:
                result.append(nums[i])
        return result

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

class Solution {
    public int[] majorityElement(int[] nums) {
        Integer cand1 = null, cand2 = null;
        int cnt1 = 0, cnt2 = 0;
        for (int v : nums) {                // elect and evict, two seats at once
            if (cand1 != null && v == cand1) {
                cnt1++;
            } else if (cand2 != null && v == cand2) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = v;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                cand2 = v;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        List<Integer> result = new ArrayList<>();
        int actual1 = 0, actual2 = 0;
        for (int v : nums) {                // surviving the vote doesn't guarantee majority — verify
            if (cand1 != null && v == cand1) actual1++;
            if (cand2 != null && v == cand2) actual2++;
        }
        if (cand1 != null && actual1 > nums.length / 3) result.add(cand1);
        if (cand2 != null && actual2 > nums.length / 3) result.add(cand2);

        int[] ans = new int[result.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = result.get(i);
        }
        return ans;
    }
}

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

class Solution {
    public int[] majorityElement(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        Set<Integer> counted = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (counted.contains(nums[i])) {
                continue;
            }
            counted.add(nums[i]);
            int cnt = 0;
            for (int j = 0; j < n; j++) {   // re-scan the whole array for this candidate
                if (nums[j] == nums[i]) {
                    cnt++;
                }
            }
            if (cnt > n / 3) {
                result.add(nums[i]);
            }
        }
        int[] ans = new int[result.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = result.get(i);
        }
        return ans;
    }
}

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

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