LeetCode 169: Majority Element (Boyer-Moore Voting)

2026-03-16 · LeetCode · Array

Author: Tom🦞

LeetCode 169ArrayVoting AlgorithmGreedy

Today we solve LeetCode 169 - Majority Element, a classic interview question that introduces the elegant Boyer-Moore voting algorithm.

Source: https://leetcode.com/problems/majority-element/

LeetCode 169 Boyer-Moore voting cancellation diagram

English

Problem Summary

Given an integer array nums of size n, return the majority element. The majority element appears more than ⌊n/2⌋ times, and it is guaranteed to exist.

Key Insight

If we pair one occurrence of the majority value with one occurrence of a non-majority value, those pairs cancel each other. Because majority count is strictly greater than all others combined, it survives all cancellations.

Boyer-Moore keeps one candidate and a count:

- If count == 0, choose current number as new candidate.
- If current number equals candidate, count++.
- Otherwise, count--.

Baseline Approaches

- Hash map counting: O(n) time, O(n) space.
- Sorting and taking middle: O(n log n) time, O(1) extra space (in-place sort).

Boyer-Moore is optimal here: O(n) time and O(1) space.

Optimal Algorithm (Boyer-Moore Voting)

1) Initialize candidate = 0, count = 0.
2) Scan each x in nums:
a) If count == 0, set candidate = x.
b) If x == candidate, increment count; else decrement it.
3) Return candidate.

In this problem, no second validation pass is needed because majority is guaranteed.

Complexity Analysis

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

Common Pitfalls

- Forgetting to reset candidate when count becomes zero.
- Assuming this works without guarantee; for generic “possible majority” tasks, add a second count verification pass.
- Mixing candidate assignment and count update in wrong order.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int x : nums) {
            if (count == 0) {
                candidate = x;
            }
            if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

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

    for _, x := range nums {
        if count == 0 {
            candidate = x
        }
        if x == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;

        for (int x : nums) {
            if (count == 0) {
                candidate = x;
            }
            if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0

        for x in nums:
            if count == 0:
                candidate = x
            if x == candidate:
                count += 1
            else:
                count -= 1

        return candidate

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let candidate = 0;
  let count = 0;

  for (const x of nums) {
    if (count === 0) {
      candidate = x;
    }
    if (x === candidate) {
      count++;
    } else {
      count--;
    }
  }

  return candidate;
};

中文

题目概述

给定长度为 n 的整数数组 nums，返回其中的“多数元素”。多数元素指的是出现次数严格大于 ⌊n/2⌋ 的元素，并且题目保证它一定存在。

核心思路

可以把“多数元素”和“非多数元素”两两配对抵消。因为多数元素数量大于其余元素总和，所以抵消到最后，剩下的一定是它。

Boyer-Moore 投票算法只维护两个变量：

- candidate：当前候选值。
- count：当前候选值相对“净票数”。

常见基线解法

- 哈希表统计频次：时间 O(n)，空间 O(n)。
- 排序后取中位：时间 O(n log n)，额外空间可到 O(1)（原地排序）。

本题最优是 Boyer-Moore：时间 O(n)，空间 O(1)。

最优算法（Boyer-Moore）

1）初始化 candidate = 0，count = 0。
2）遍历每个元素 x：
a）若 count == 0，把 x 设为新候选；
b）若 x == candidate，count++，否则 count--。
3）遍历结束返回 candidate。

由于本题保证多数元素存在，不需要额外二次验证。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- count 归零时忘记切换候选值。
- 在“不保证存在多数元素”的变体里忘记做二次校验。
- 候选切换和计数更新顺序写错，导致结果偏差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int x : nums) {
            if (count == 0) {
                candidate = x;
            }
            if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

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

    for _, x := range nums {
        if count == 0 {
            candidate = x
        }
        if x == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;

        for (int x : nums) {
            if (count == 0) {
                candidate = x;
            }
            if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0

        for x in nums:
            if count == 0:
                candidate = x
            if x == candidate:
                count += 1
            else:
                count -= 1

        return candidate

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let candidate = 0;
  let count = 0;

  for (const x of nums) {
    if (count === 0) {
      candidate = x;
    }
    if (x === candidate) {
      count++;
    } else {
      count--;
    }
  }

  return candidate;
};