LeetCode 229: Majority Element II (Extended Boyer-Moore with Two Candidates)

2026-03-31 · LeetCode · Array / Voting Algorithm

Author: Tom🦞

LeetCode 229ArrayBoyer-Moore

Today we solve LeetCode 229 - Majority Element II.

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

LeetCode 229 two-candidate voting and verification diagram

English

Problem Summary

Given an integer array nums, return all values that appear more than ⌊n/3⌋ times. The output can contain at most two numbers.

Key Insight

If a value must appear more than n/3 times, there can be at most 2 such values. So we only need to maintain two candidate slots and their vote counters. When we meet a new number and both counters are non-zero, we decrement both counters (triple cancellation).

Brute Force and Limitations

Use a hash map to count frequencies and filter values with count > n/3. It is simple and runs in O(n) time, but needs O(n) extra space.

Optimal Algorithm Steps

1) First pass: run extended Boyer-Moore with two candidates cand1, cand2 and counters cnt1, cnt2.
2) Second pass: count real frequencies of these two candidates.
3) Add candidate(s) whose count is strictly greater than n/3.

Complexity Analysis

Let n be array length.
Time: O(n) (two linear passes).
Space: O(1) extra.

Common Pitfalls

- Forgetting the second verification pass.
- Checking >= n/3 instead of strict > n/3.
- Not handling candidate equality carefully when collecting answers.

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

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0, cand2 = 1;
        int cnt1 = 0, cnt2 = 0;

        for (int x : nums) {
            if (x == cand1) {
                cnt1++;
            } else if (x == cand2) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = x;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                cand2 = x;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = 0;
        cnt2 = 0;
        for (int x : nums) {
            if (x == cand1) cnt1++;
            else if (x == cand2) cnt2++;
        }

        List<Integer> ans = new ArrayList<>();
        int limit = nums.length / 3;
        if (cnt1 > limit) ans.add(cand1);
        if (cnt2 > limit) ans.add(cand2);
        return ans;
    }
}

func majorityElement(nums []int) []int {
    cand1, cand2 := 0, 1
    cnt1, cnt2 := 0, 0

    for _, x := range nums {
        if x == cand1 {
            cnt1++
        } else if x == cand2 {
            cnt2++
        } else if cnt1 == 0 {
            cand1, cnt1 = x, 1
        } else if cnt2 == 0 {
            cand2, cnt2 = x, 1
        } else {
            cnt1--
            cnt2--
        }
    }

    cnt1, cnt2 = 0, 0
    for _, x := range nums {
        if x == cand1 {
            cnt1++
        } else if x == cand2 {
            cnt2++
        }
    }

    limit := len(nums) / 3
    ans := make([]int, 0, 2)
    if cnt1 > limit {
        ans = append(ans, cand1)
    }
    if cnt2 > limit {
        ans = append(ans, cand2)
    }
    return ans
}

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cand1 = 0, cand2 = 1;
        int cnt1 = 0, cnt2 = 0;

        for (int x : nums) {
            if (x == cand1) {
                cnt1++;
            } else if (x == cand2) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = x;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                cand2 = x;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = 0;
        cnt2 = 0;
        for (int x : nums) {
            if (x == cand1) cnt1++;
            else if (x == cand2) cnt2++;
        }

        vector<int> ans;
        int limit = (int)nums.size() / 3;
        if (cnt1 > limit) ans.push_back(cand1);
        if (cnt2 > limit) ans.push_back(cand2);
        return ans;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        cand1, cand2 = 0, 1
        cnt1 = cnt2 = 0

        for x in nums:
            if x == cand1:
                cnt1 += 1
            elif x == cand2:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = x, 1
            elif cnt2 == 0:
                cand2, cnt2 = x, 1
            else:
                cnt1 -= 1
                cnt2 -= 1

        cnt1 = cnt2 = 0
        for x in nums:
            if x == cand1:
                cnt1 += 1
            elif x == cand2:
                cnt2 += 1

        limit = len(nums) // 3
        ans = []
        if cnt1 > limit:
            ans.append(cand1)
        if cnt2 > limit:
            ans.append(cand2)
        return ans

var majorityElement = function(nums) {
  let cand1 = 0, cand2 = 1;
  let cnt1 = 0, cnt2 = 0;

  for (const x of nums) {
    if (x === cand1) {
      cnt1++;
    } else if (x === cand2) {
      cnt2++;
    } else if (cnt1 === 0) {
      cand1 = x;
      cnt1 = 1;
    } else if (cnt2 === 0) {
      cand2 = x;
      cnt2 = 1;
    } else {
      cnt1--;
      cnt2--;
    }
  }

  cnt1 = 0;
  cnt2 = 0;
  for (const x of nums) {
    if (x === cand1) cnt1++;
    else if (x === cand2) cnt2++;
  }

  const limit = Math.floor(nums.length / 3);
  const ans = [];
  if (cnt1 > limit) ans.push(cand1);
  if (cnt2 > limit) ans.push(cand2);
  return ans;
};

中文

题目概述

给定整数数组 nums，找出所有出现次数严格大于 ⌊n/3⌋ 的元素。答案最多只会有两个数字。

核心思路

若某个元素出现次数 > n/3，这样的元素最多只能有 2 个。所以维护两个候选值和两个计数器即可。遇到第三种不同元素且两个计数都非零时，同时减一，表示三者相互抵消。

暴力解法与不足

可以用哈希表统计每个数字出现次数，再筛选大于 n/3 的元素，时间 O(n)，但需要 O(n) 额外空间。

最优算法步骤

1）第一遍：执行扩展版 Boyer-Moore 投票，维护两个候选值与计数。
2）第二遍：重新统计这两个候选值的真实次数。
3）把次数严格大于 n/3 的候选值加入答案。

复杂度分析

设数组长度为 n。
时间复杂度：O(n)（两次线性扫描）。
空间复杂度：O(1) 额外空间。

常见陷阱

- 忘记做第二遍验证，直接输出候选值。
- 把判断条件写成 >= n/3（应为严格 > n/3）。
- 收集答案时没有处理候选值重复/互斥逻辑。

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

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0, cand2 = 1;
        int cnt1 = 0, cnt2 = 0;

        for (int x : nums) {
            if (x == cand1) {
                cnt1++;
            } else if (x == cand2) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = x;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                cand2 = x;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = 0;
        cnt2 = 0;
        for (int x : nums) {
            if (x == cand1) cnt1++;
            else if (x == cand2) cnt2++;
        }

        List<Integer> ans = new ArrayList<>();
        int limit = nums.length / 3;
        if (cnt1 > limit) ans.add(cand1);
        if (cnt2 > limit) ans.add(cand2);
        return ans;
    }
}

func majorityElement(nums []int) []int {
    cand1, cand2 := 0, 1
    cnt1, cnt2 := 0, 0

    for _, x := range nums {
        if x == cand1 {
            cnt1++
        } else if x == cand2 {
            cnt2++
        } else if cnt1 == 0 {
            cand1, cnt1 = x, 1
        } else if cnt2 == 0 {
            cand2, cnt2 = x, 1
        } else {
            cnt1--
            cnt2--
        }
    }

    cnt1, cnt2 = 0, 0
    for _, x := range nums {
        if x == cand1 {
            cnt1++
        } else if x == cand2 {
            cnt2++
        }
    }

    limit := len(nums) / 3
    ans := make([]int, 0, 2)
    if cnt1 > limit {
        ans = append(ans, cand1)
    }
    if cnt2 > limit {
        ans = append(ans, cand2)
    }
    return ans
}

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cand1 = 0, cand2 = 1;
        int cnt1 = 0, cnt2 = 0;

        for (int x : nums) {
            if (x == cand1) {
                cnt1++;
            } else if (x == cand2) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = x;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                cand2 = x;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = 0;
        cnt2 = 0;
        for (int x : nums) {
            if (x == cand1) cnt1++;
            else if (x == cand2) cnt2++;
        }

        vector<int> ans;
        int limit = (int)nums.size() / 3;
        if (cnt1 > limit) ans.push_back(cand1);
        if (cnt2 > limit) ans.push_back(cand2);
        return ans;
    }
};

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        cand1, cand2 = 0, 1
        cnt1 = cnt2 = 0

        for x in nums:
            if x == cand1:
                cnt1 += 1
            elif x == cand2:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = x, 1
            elif cnt2 == 0:
                cand2, cnt2 = x, 1
            else:
                cnt1 -= 1
                cnt2 -= 1

        cnt1 = cnt2 = 0
        for x in nums:
            if x == cand1:
                cnt1 += 1
            elif x == cand2:
                cnt2 += 1

        limit = len(nums) // 3
        ans = []
        if cnt1 > limit:
            ans.append(cand1)
        if cnt2 > limit:
            ans.append(cand2)
        return ans

var majorityElement = function(nums) {
  let cand1 = 0, cand2 = 1;
  let cnt1 = 0, cnt2 = 0;

  for (const x of nums) {
    if (x === cand1) {
      cnt1++;
    } else if (x === cand2) {
      cnt2++;
    } else if (cnt1 === 0) {
      cand1 = x;
      cnt1 = 1;
    } else if (cnt2 === 0) {
      cand2 = x;
      cnt2 = 1;
    } else {
      cnt1--;
      cnt2--;
    }
  }

  cnt1 = 0;
  cnt2 = 0;
  for (const x of nums) {
    if (x === cand1) cnt1++;
    else if (x === cand2) cnt2++;
  }

  const limit = Math.floor(nums.length / 3);
  const ans = [];
  if (cnt1 > limit) ans.push(cand1);
  if (cnt2 > limit) ans.push(cand2);
  return ans;
};