A replica set elects a primary by strict majority: the node id that more than half the members name. The intern hashed every ballot into a frequency map. Five nodes were instant. Five thousand synthetic ballots in a chaos drill were still allocating buckets when the election timeout fired.

Majority Element asks for the value that appears more than n / 2 times. An array already gives a[i] for free. Nested recount uses that and still pays O(n²). A frequency map is the honest extra-space answer. Sorting and reading nums[n / 2] is also correct under the guarantee — the majority must occupy the middle slot — but sorting permutes an array you were not asked to reorder.

This is an interview writeup, not a hashing lecture. Here we only care about cancelling votes: a majority cannot be fully cancelled by the rest, so two integers — a candidate and a leftover count — replace the map.

The problem

Given an int[] nums of length n, return the value that occurs more than n / 2 times. That value is guaranteed to exist. You may assume n >= 1.

nums = [12, 5, 12, 12, 8]   →  12    12 appears 3 times, n/2 is 2
nums = [4, 4, 9, 4]         →  4
nums = [7, 7, 7]            →  7

Note: More than n / 2 is a strict majority, not a plurality. In [1, 1, 2, 2, 3] nothing qualifies; that input is excluded by the guarantee. Integer division is the bar: for n = 5 you need at least 3 occurrences.

Nested recount is the honest brute force

For each index, count how many times that value appears; the first whose count exceeds n / 2 is the answer. Correct. Quadratic.

int majorityNested(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) {
                count++;
            }
        }
        if (count > n / 2) {
            return nums[i];
        }
    }
    throw new IllegalStateException("no majority");
}

At n = 20 this is a rounding error. A HashMap of frequencies is the same idea with extra space: one pass, then return the key whose count exceeds n / 2. At n in the hundreds of thousands you paid either nested scans or a map for a question two integers answer in a single pass: which value still has uncancelled votes?

One pass: a candidate and a count that cancel

Walk left to right. Two running values:

  • candidate — the value that still has uncancelled votes.
  • count — how many of those leftover votes it holds.

When count hits 0, the next value becomes the new candidate. Matching values increment; others decrement (they cancel one vote). Because a majority occupies more than half the slots, it cannot be fully cancelled: whatever is left standing is that value. Interviewers call this Boyer-Moore voting — a candidate and a leftover count, not a frequency table.

nums = [12, 5, 12, 12, 8]

i=0  v=12  count=0  take candidate=12, count=1
i=1  v=5   5≠12     count=0      12 and 5 cancel
i=2  v=12  count=0  take candidate=12, count=1
i=3  v=12  same     count=2
i=4  v=8   8≠12     count=1      leftover candidate is 12

The Java is that walk. When count is 0 you adopt v first, then the increment lands on the new candidate:

int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int v : nums) {
        if (count == 0) {
            candidate = v;
        }
        count += (v == candidate) ? 1 : -1;
    }
    return candidate;
}

Time is O(n) — one pass, constant work per index. Space is O(1) besides the two running integers.

Note: count is leftover votes, not the true frequency. On the trace above the majority 12 appears three times; the walk ends at count = 1. Do not return count. The 0 seed for candidate is harmless: the first element always takes over because count starts at 0.

What interviewers usually poke next

  • No majority guarantee. The leftover candidate might be a plurality. Second pass: count it, accept only if the count exceeds n / 2. If it fails, say so — do not pretend the vote proved existence.
  • Majority n / 3. At most two such values. Keep two candidates and two counts, then verify both. Same cancel idea; different leftover set. Do not invent the full walk unless they ask.
  • Return an index, not the value. Voting yields the value. Scan once more for the first (or any) index where nums[i] == candidate.
  • HashMap anyway. Name the space bill out loud. It is the honest extra-space answer, not the intended one when they asked for linear time and constant extra memory.
  • Sort and pick the middle. Legal under the guarantee. O(n log n) time, and you permute the input. Say why the vote is still the default when they did not ask you to reorder.

You are done with this problem when you can say, out loud, why nested recount and a frequency map are correct, why sorting finds the middle slot and still rewrites the array, and why cancelling votes leaves the majority standing.