Majority Element LeetCode 169 Deep Dive

LeetCode 169 — Majority Element — gives you an integer array of size n and asks you to return the majority element: the element that appears more than n/2 times. The problem guarantees that a majority element always exists, which is a critical constraint that unlocks the Boyer-Moore Voting Algorithm as a valid solution without a verification pass.

The naive approach — counting every element with a hash map — runs in O(n) time but uses O(n) extra space. Sorting runs in O(n log n) time but reveals the answer elegantly at index n//2. The challenge is to find an O(n) time, O(1) space solution, and Boyer-Moore delivers exactly that by treating the problem as a vote count rather than a frequency count.

Majority Element is a foundational problem that appears in interviews at all levels. It tests whether you know the Boyer-Moore algorithm specifically, or can derive it by reasoning about what happens when the majority element "battles" all other elements and always has enough votes left over to win.

The Boyer-Moore Voting Algorithm maintains two variables: a candidate and a count. Initialize both to 0 (or candidate to any value and count to 0). Iterate through the array: if count is 0, set the current element as the new candidate. If the current element equals the candidate, increment count. Otherwise, decrement count. After the full pass, the candidate holds the majority element.

The algorithm works because the majority element appears more than n/2 times. Even if every occurrence of the majority element is "cancelled" by a different element, the majority still has more votes than all other elements combined. No matter how the non-majority elements are arranged, they cannot permanently reduce the majority candidate's count to zero and keep it there.

The implementation is strikingly concise: two variables, one loop, no extra data structures. Python: candidate, count = 0, 0; for num in nums: if count == 0: candidate = num; count += 1 if num == candidate else -1; return candidate. Java: a straightforward enhanced for-loop with the same logic. Time is O(n), space is O(1).

The correctness of Boyer-Moore rests on one fact: the majority element appears more than n/2 times, so it appears more than all other elements combined. Count every occurrence of the majority element as +1 and every occurrence of any other element as -1. The total sum is positive — specifically, 2*count(majority) - n > 0. This means the majority "wins" even against a perfectly coordinated opposition.

When count reaches 0, we have seen an equal number of votes for and against the current candidate. At that point, none of the elements seen so far can change the eventual winner, because they cancel perfectly. The algorithm discards that balanced prefix and restarts. The majority element's vote surplus is so large that it wins every sub-contest where it participates.

A subtle but important point: Boyer-Moore finds the majority candidate, not a verified majority. If the problem did not guarantee a majority exists, you would need a second pass to count occurrences of the candidate and confirm count > n/2. LeetCode 169 guarantees existence, so the second pass is optional here — but always required in the general case.

Sorting approach: sort the array in O(n log n) time. Because the majority element appears more than n/2 times, it must occupy the center of the sorted array. Return nums[n//2] (0-indexed). This works because no matter how minority elements are distributed, the majority element fills more than half the positions and must include the median. Space is O(1) if sorting in place.

HashMap approach: iterate through the array and count the frequency of each element using a dictionary or hash map. Return the first element whose count exceeds n//2. Time O(n), space O(n). This is the most intuitive approach and easy to implement, but uses linear extra space, which is suboptimal.

Random sampling: pick a random element, count its occurrences in O(n). If count > n//2, return it. Otherwise retry. Expected time O(n) because the majority element appears in more than half the positions, so any random pick has > 50% probability of hitting the majority. Worst-case unbounded but expected O(n). Divide and conquer: recursively find majority in left and right halves; if they agree, that is the answer; if not, count both in the full range; O(n log n) time.

Consider nums = [2, 2, 1, 1, 1, 2, 2]. The majority element is 2 (appears 4 times out of 7). Walk through Boyer-Moore: start with candidate=None, count=0.

Element 2: count==0 so candidate=2, count=1. Element 2: same as candidate, count=2. Element 1: different, count=1. Element 1: different, count=0. Element 1: count==0 so candidate=1, count=1. Element 2: different, count=0. Element 2: count==0 so candidate=2, count=1. Final candidate=2. Correct.

Notice that candidate temporarily switched to 1 when count hit 0 at index 3. This is fine — the majority element (2) still wins because it has enough remaining occurrences to reclaim the candidacy. The algorithm self-corrects because the true majority always has a surplus of votes.

Python Boyer-Moore: candidate, count = 0, 0; for num in nums: if count == 0: candidate = num; count += (1 if num == candidate else -1); return candidate. Five lines, no imports, no extra data structures. Time O(n), space O(1). Python also offers a one-liner: from collections import Counter; return Counter(nums).most_common(1)[0][0]. This is O(n) time O(n) space — elegant for production but not the interview answer.

Java Boyer-Moore: public int majorityElement(int[] nums) { int candidate = 0, count = 0; for (int num : nums) { if (count == 0) candidate = num; count += (num == candidate) ? 1 : -1; } return candidate; } Four lines inside the method, one loop, no imports. Time O(n), space O(1). Java also has Arrays.sort(nums); return nums[nums.length/2]; for the sorting approach.

Both implementations are clean enough to write from memory in an interview under pressure. The key is remembering the two-variable pattern: candidate and count, with the reset-when-zero rule. Practice writing it without looking — it is short enough to memorize and powerful enough to impress.

Majority Element II (LeetCode 229) generalizes the problem: find all elements appearing more than n/3 times. At most two such elements can exist. Boyer-Moore generalizes elegantly: maintain two candidates and two counts, applying the same voting logic. When count reaches 0, reset that candidate. After the pass, verify both candidates with a counting pass since n/3 existence is not guaranteed.

Top K Frequent Elements (LeetCode 347) replaces the majority threshold with a frequency rank. Boyer-Moore does not directly apply, but bucket sort (frequency → list of elements) solves it in O(n) time O(n) space. Single Number (LeetCode 136) uses XOR rather than voting, but both are "find the odd element out" problems that exploit the mathematical structure of the input.

The voting algorithm family is a rich interview topic: Boyer-Moore for majority, its generalization for supermajority, and the connection to streaming algorithms where you cannot store the full input. If you see any problem involving "find the element that dominates by count," Boyer-Moore or a variant is the first algorithm to consider.