Back to Problem
Official 1151 views

Editorial: Majority Element

by admin ·

20

1 Intuition

Pairing off different values cancels them; the majority value survives.

2 Approach

Boyer–Moore voting: keep a candidate and a counter. Increment on a match, decrement otherwise, and switch candidate when the counter hits zero.

3 Complexity Analysis

Time O(n), Space O(1).

4 Solution Code 

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate, count = None, 0
        for x in nums:
            if count == 0:
                candidate = x
            count += 1 if x == candidate else -1
        return candidate

5 Code Walkthrough

The reference solution below implements the approach step by step.