169. Majority Element

Quick Identifier

• Topic: arrays-hashing
• Pattern: Boyer-Moore Voting Algorithm
• Hint: If you have a room full of people, and more than half of them belong to faction A, they will always win a 1-on-1 fight against the other factions combined. Let different elements "destroy" each other. The survivor is the majority.
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• LeetCode: 169

Quick Sights

• Time Complexity: O(n). We stream through the array exactly once.
• Space Complexity: O(1). We only maintain two variables: a candidate and a count.
• Core Mechanism: Maintain a candidate element and a count (initialized to 0). Iterate through the array.
  • If count == 0, set the candidate to the current element.
  • If the current element equals the candidate, increment count.
  • If the current element does not equal the candidate, decrement count. Because the majority element appears more than ⌊n / 2⌋ times, its count will mathematically outlast all other elements combined.

Concept Explanation

As a senior engineer, sorting or using a Hash Map are trivial $O(n \log n)$ or $O(n)$ space solutions. The $O(1)$ space requirement demands a specific mathematical insight: The Boyer-Moore Voting Algorithm.

1. The Arena Analogy: Imagine every element in the array is a soldier. The majority element is an army that has more soldiers than all other armies combined.
2. Mutual Destruction: Send soldiers into the arena two at a time. If they are from the same army, they join forces (count goes up). If they are from different armies, they kill each other (count goes down).
3. The Mathematical Guarantee: Even if all the minority armies gang up on the majority army, the majority army has enough soldiers to sacrifice 1-for-1 against every single minority soldier, and still have soldiers left over.
4. The Implementation: The count variable tracks the health of the current reigning champion (candidate). When count hits 0, the champion is dead, and the very next element becomes the new champion. By the end of the array, the last surviving champion is mathematically guaranteed to be the majority.

(Note: This algorithm ONLY works if a strict majority > ⌊n / 2⌋ is guaranteed to exist. If a majority might not exist, you must do a second $O(n)$ pass to verify the final candidate's true count).

Diagram

This flowchart outlines the Boyer-Moore mutual destruction logic.

Study Pattern (SDE3+)

• 0–3 min: Immediately name-drop Boyer-Moore. Explain the $O(1)$ space requirement and outline the "mutual destruction" mental model. It proves you understand the mathematical invariant rather than just memorizing the code.
• Implementation pass: The code is almost suspiciously simple. Ensure you check count == 0 before doing the num == candidate comparison, so that a newly crowned candidate immediately gets its count bumped to 1.
• 5 min extension: Discuss "Majority Element II" (LeetCode 229), which asks for elements appearing more than ⌊n / 3⌋ times. Explain that the Boyer-Moore logic scales: you can have at most two such elements, so you just maintain two candidates and two counts. If a number doesn't match either candidate, you decrement both counts.

Approaches

• Hash Map — Count frequencies of all elements. Time: $O(n)$, Space: $O(n)$. Fails the $O(1)$ space bonus constraint.
• Sorting — Sort the array and return nums[n/2]. Time: $O(n \log n)$, Space: $O(1)$. Suboptimal time.
• Boyer-Moore Voting — Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func majorityElement(nums []int) int {
	var candidate int
	count := 0

	for _, num := range nums {
		// If the current candidate has been entirely defeated,
		// the next element becomes the new candidate.
		if count == 0 {
			candidate = num
		}

		// If it's our candidate, reinforcement. If not, mutual destruction.
		if num == candidate {
			count++
		} else {
			count--
		}
	}

	// The problem guarantees a majority element exists,
	// so the final surviving candidate is the answer.
	return candidate
}

JavaScript

function majorityElement(nums) {
	let candidate = null;
	let count = 0;

	for (const num of nums) {
		// Elect a new candidate if the previous one died
		if (count === 0) {
			candidate = num;
		}

		// Reinforce or mutually destroy
		if (num === candidate) {
			count++;
		} else {
			count--;
		}
	}

	return candidate;
}

Walkthrough

Input: nums = [2, 2, 1, 1, 1, 2, 2]

Output: 2. (The count doesn't represent the actual total frequency; it represents the net survivor count).

Edge Cases

• Array length of 1. The count goes to 1, and the single element is correctly returned.
• The majority element is all at the beginning, or all at the end. The math holds regardless of permutation.

Pitfalls

• Assuming the final count variable holds the total frequency of the majority element. It does not. It only holds the surviving margin. If nums = [2, 2, 2, 1, 1], the count is 1, even though 2 appears three times.
• Forgetting that Boyer-Moore only finds the potential majority. Because the problem explicitly states "You may assume that the majority element always exists", we don't need a second pass to verify. If that guarantee was missing, we would need to loop again to count occurrences of candidate to ensure it actually exceeds n/2.

Similar Problems

• 229. Majority Element II — The $O(1)$ space variant looking for elements > ⌊n / 3⌋. Uses two candidates.
• 053. Maximum Subarray — Another $O(n)$ time, $O(1)$ space streaming algorithm that requires maintaining a local invariant state.

Mind-Map Tags

#arrays #boyer-moore #majority #constant-space #voting #stream