• n == nums.length
• 1 <= n <= 5 × 10⁴
• -10⁹ <= nums[i] <= 10⁹
• The majority element always exists in the input

First, pin down the word majority, because it is stricter than it sounds. An element is the majority only if it occupies more than half of all positions. The notation ⌊n / 2⌋ means "n divided by 2, rounded down", so with n = 7 elements the bar is more than 3 — at least 4 occurrences. Being merely the most frequent value is not enough: in [1, 1, 2, 3] the value 1 is the most common, yet it holds only 2 of the 4 positions, which is not more than half — that array has no majority at all. Our input is guaranteed to contain one, and every idea below quietly leans on how strong that promise is: the majority outnumbers all other values combined.

Sorting rearranges the array so that equal values end up standing next to each other — each distinct value becomes one solid, contiguous block. Now think about the majority's block: it is longer than half the array. Try to place a block longer than half anywhere inside the array — flush left, flush right, anywhere between — and there is no way for it to avoid covering the middle position. So after sorting, whatever sits at index n // 2 must be the majority.

nums.sort()
return nums[len(nums) // 2]

Correct and pleasantly short — but sorting costs O(N log N) time, noticeably more than a single pass when n is large. And there is something wasteful about it: we don't need the array in order. We need one single fact about it, and we paid for a full reordering to learn that fact.

The direct approach: sweep the array once and tally how many times each value occurs, keeping one counter per distinct value in a hash map (the constant-time lookup structure we met in Two Sum). The moment any counter climbs past ⌊n / 2⌋, that value is the answer.

counts = {}
for num in nums:
    counts[num] = counts.get(num, 0) + 1
    if counts[num] > len(nums) // 2:
        return num

One pass, so O(N) time — an improvement. But the map may end up holding a counter for nearly every distinct value, which is O(N) extra memory. In an interview this is exactly where the follow-up lands: "Good. Now do it without the extra memory." To get there we finally have to cash in the guarantee the problem handed us.

Split the array, in your head, into two camps: every copy of the majority value in one camp, and everything else — all the other values lumped together — in the other. The guarantee says the majority camp is strictly larger. Now repeatedly remove one member from each camp, one for one. Every removal costs each camp exactly one member, and the majority camp started strictly bigger — so the mixed camp must run out first, and whatever survives the pairing is made purely of majority copies. Here is the beautiful part: we never needed to know which value is the majority to run this elimination. Survival itself identifies it.

The Boyer-Moore algorithm performs the pairing with just two variables and a single pass — no memory that grows with the input. It carries a current candidate and a count of how many of the candidate's copies are so far unmatched:
- The next element equals the candidate: one more unmatched copy, count goes up by 1.
- The next element differs: it cancels one carried copy — a one-for-one elimination — and count goes down by 1.
- Count is 0: everything seen so far has cancelled out, so adopt the current element as the new candidate.

candidate = None
count = 0
for num in nums:
    if count == 0:
        candidate = num
    count += (1 if num == candidate else -1)
return candidate

The uncomfortable question — and the entire heart of this algorithm — is: how can it be safe to throw away the candidate whenever count reaches 0? Couldn't we accidentally discard the true majority? Look closely at what count = 0 means: within the stretch of elements consumed since the last adoption, exactly half matched the then-candidate and half did not. In any such half-and-half stretch, the true majority value can account for at most half of the elements — if it was the candidate, it was exactly half; if it wasn't, all of its copies sit inside the other half. And losing at most half of a discarded stretch can never cost a strict majority its lead: it still holds more than half of everything that remains. That invariant survives every single reset, so after the last element the surviving candidate can only be the majority value.

Boyer-Moore's answer is trustworthy only because the problem guarantees a majority exists. Run the same code on [1, 2, 3] — an array with no majority — and it still cheerfully returns a candidate (3, as it happens) that means nothing. If that guarantee were removed, the fix is one extra O(N) pass: count the candidate's actual occurrences and confirm they exceed ⌊n / 2⌋, still using O(1) space. Mentioning this unprompted is a strong interview signal — it shows you know why the algorithm works, not merely its moves. And carry away the deeper lesson: the O(1)-space trick was not generic cleverness. It worked by cashing in an unusually strong promise printed in the problem statement. Whenever a problem hands you a guarantee like that, ask what the guarantee lets you throw away. (The same voting idea, run with two candidates, even solves the harder version: find all elements appearing more than n / 3 times.)