💬 Discord
Sign In
NeetCode #46LC-169EasyArrays & HashingNC 250
← Back to All Problems

#46 · #169 · Majority Element(多数元素)

📌 Problem Statement & Constraints

Given an array nums of size n, return the majority element -- the element that appears more than n / 2 times. You may assume the majority element always exists. Constraints: 1 <= n <= 5 * 10^4, -10^9 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Boyer-Moore voting algorithm, the expected O(n) time / O(1) space answer.
  2. Maintain a candidate and a count. For each element: if count == 0, adopt the element as the new candidate and set count = 1; otherwise increment count if it matches the candidate, else decrement it.
  3. Intuition: think of pairing each occurrence of the majority element with a different element and cancelling them. Because the majority appears more than n/2 times, it cannot be fully cancelled -- it survives as the final candidate.
  4. The problem guarantees a majority exists, so no verification pass is needed. Without that guarantee, a second pass counting the candidate would be required.

💻 Benchmark Python3 Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for x in nums:
            if count == 0:
                candidate = x       # adopt a new candidate
                count = 1
            elif x == candidate:
                count += 1
            else:
                count -= 1          # cancel one vote
        return candidate


# Without the existence guarantee, a verification pass is mandatory
class Solution2:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for x in nums:
            if count == 0:
                candidate, count = x, 1
            else:
                count += 1 if x == candidate else -1
        # verify
        if nums.count(candidate) * 2 > len(nums):
            return candidate
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass. The hash-map alternative is also O(n) but uses O(n) space.
💾 Space Complexity
O(1): only two scalar variables, which is the point of the voting algorithm.

⚠️ Interview Pitfalls & Follow-ups

  • Using a hash map or Counter: correct and O(n), but O(n) space. Mention it as the naive baseline, then present voting.
  • Sorting and taking the middle element: O(n log n); the element at index n // 2 is indeed the majority, but the time complexity is worse.
  • Forgetting the verification pass in the general case: without the guarantee, voting returns a candidate that may not be the majority. Always verify unless the statement promises existence.
  • Confusing the majority threshold: it is strictly more than n / 2, which is what makes at most one majority element possible.