Skip to content
LEETFLIX

Majority Element

EasyArrayHashingD&CSorting
Solve on LeetCode

Easy · Boyer–Moore vote. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 169. Majority Element. The copyrighted prompt is on LeetCode. This page is a working Boyer–Moore vote for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

nums =
[3, 2, 3]

Output

3

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Boyer–Moore majority vote

Keep a candidate and a count. Matching values increment the count; mismatches decrement. When the count hits 0, pick a new candidate. The majority survives.

Every minority vote cancels one majority vote. Because the majority appears > n/2 times, it cannot be cancelled away.

Algorithm

  1. Start with no candidate.
  2. For each x: if count is 0, x becomes the candidate; then ±1 the count.
  3. Return the candidate.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def majorityElement(self, nums: list[int]) -> int:        cand = 0        count = 0        for x in nums:            if count == 0:                cand = x            count += 1 if x == cand else -1        return cand
Watch this run

03

Interactive walkthrough

Playing “Boyer–Moore majority vote”. Edit the input, hit Run, then scrub.

Approach: Boyer–Moore majority vote

Loading animation…