{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Majority Element – Solution & Complexity

Interview solutions
/
Majority Element

1. Understand the Majority Guarantee

  • A majority element appears more than half of the array length.
  • The problem guarantees such an element exists, so the final answer does not need a failure case.
  • The challenge is finding it efficiently without counting every value in extra storage.

2. Start with Counting

  • A straightforward solution stores how often each number appears.
  • As soon as a count becomes greater than len(nums) // 2, that number is the answer.
  • This is linear time, but it uses O(n) extra space for the dictionary.
def majority_element(nums):
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > len(nums) // 2:
            return num

3. Use Boyer-Moore Voting

  • Pair each occurrence of a candidate with a different value and cancel both out.
  • Because the majority element appears more than all other values combined, it cannot be fully canceled.
  • Keep only a current candidate and a vote count.

4. Update Candidate and Votes

  • When the vote count is zero, choose the current number as the new candidate.
  • Add one vote when the current number matches the candidate.
  • Subtract one vote when it differs, representing a cancellation.
def majority_element(nums):
    candidate = None
    votes = 0
    for num in nums:
        if votes == 0:
            candidate = num
        votes += 1 if num == candidate else -1
    return candidate

5. Final Complete Solution

  • The candidate left after all cancellations is the guaranteed majority element.
  • Time complexity is O(n) because each number is processed once.
  • Space complexity is O(1) because only two variables are stored.
def majority_element(nums: list[int]) -> int:
    candidate = None
    votes = 0

    for num in nums:
        if votes == 0:
            candidate = num
        votes += 1 if num == candidate else -1

    return candidate

FAQ

See also:

Practice Majority Element online (run code in the browser)Contains Duplicate solution (easy)Two Sum solution (easy)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?