169. Majority Element

At a Glance

• Topic: arrays-hashing
• Pattern: Boyer–Moore voting
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 169

Problem (one-liner)

Given an array numbers of length n, return the value that appears strictly more than ⌊n/2⌋ times. A majority element always exists per problem.

Recognition Cues

• "Majority element", "more than half the array"
• O(1) extra space ask → Boyer–Moore; else map counts

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — count each value — O(n²) with linear scan per element.
• Better — hash map counts — O(n) time / O(n) space.
• Optimal — Boyer–Moore: stream with canceling pairs — O(n) time / O(1) space.

Optimal Solution

Go

package main

func majorityElement(numbers []int) int {
	candidate := 0
	balance := 0
	for _, value := range numbers {
		if balance == 0 {
			candidate = value
		}
		if value == candidate {
			balance++
		} else {
			balance--
		}
	}
	return candidate
}

JavaScript

function majorityElement(numbers) {
	let candidate = 0;
	let balance = 0;
	for (const value of numbers) {
		if (balance === 0) {
			candidate = value;
		}
		if (value === candidate) {
			balance++;
		} else {
			balance--;
		}
	}
	return candidate;
}

Walkthrough

numbers = [2,2,1,1,1,2,2] — majority is 2.

Final candidate 2 (majority survives cancellations).

Edge Cases

• Length 1 — single element is majority.
• All same value — trivial.

Pitfalls

• Boyer–Moore without second pass when majority not guaranteed (here it is).
• Using XOR tricks incorrectly on multiset.

Similar Problems

• 053. Maximum Subarray — linear scan with running state.
• 217. Contains Duplicate — frequency / dominance checks.
• 001. Two Sum — map-based counting alternative for majority.

Variants

• Majority II (> n/3).
• Verify majority with second pass count.

Mind-Map Tags

#boyer-moore #majority #linear #constant-space #voting