Find Majority Element in Array —
Boyer-Moore Voting Algorithm Explained Simply

01 Introduction

The majority element problem shows up constantly in coding interviews — at Amazon, Google, Microsoft, and just about every other company that asks DSA questions. It looks easy on the surface. Most beginners grab a nested loop or a dictionary right away. But the real trick? There's an algorithm that solves it in a single pass with no extra memory at all.

That algorithm is called the Boyer-Moore Voting Algorithm, and once you understand how it works, it becomes one of those patterns you never forget. This guide walks you through every approach — from brute force to the optimal solution — step by step, with a dry run, Python code, and everything you'd need to confidently explain this in an interview.

02 Problem Statement

Given an array of integers nums of size n, find the element that appears more than n/2 times. This element is called the majority element. You may assume that the majority element always exists in the array.

Example 1

Example 2

03 Input / Output Format

04 Constraints

05 Why This Problem Matters

06 Naive Approach — Brute Force O(n²)

The simplest thing you can do: for each element, count how many times it appears in the array by scanning the whole array again. If the count exceeds n/2, return that element.

# Brute Force — O(n²) time, O(1) space
def majority_brute(nums):
    n = len(nums)
    for i in range(n):
        count = 0
        for j in range(n):
            if nums[j] == nums[i]:
                count += 1
        if count > n // 2:
            return nums[i]
    return -1  # No majority element found

07 Better Approach — HashMap / Dictionary O(n)

Use a dictionary to count the frequency of each element in one pass. Then check which element has a count greater than n/2. This is much better than brute force but still uses O(n) extra space.

# HashMap Approach — O(n) time, O(n) space
def majority_hashmap(nums):
    n = len(nums)
    freq = {}

    for num in nums:
        freq[num] = freq.get(num, 0) + 1

    for num, count in freq.items():
        if count > n // 2:
            return num

    return -1

08 Optimal — Boyer-Moore Voting Algorithm

This is the clever one. The key insight is: if you pair up every occurrence of the majority element with a different element and cancel them out, you'll always have the majority element left over.

Here's how it works step by step:

• Start with candidate = None and count = 0
• For each element in the array:
  • If count == 0, set this element as the new candidate
  • If the element equals the candidate, increment count
  • Otherwise, decrement count (they cancel each other)
• At the end, candidate holds the majority element

# Boyer-Moore Voting Algorithm — O(n) time, O(1) space
def majority_boyer_moore(nums):
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num  # New candidate selected
        if num == candidate:
            count += 1      # Same as candidate — support it
        else:
            count -= 1      # Different — cancel one vote

    return candidate

Just 8 lines. No extra space. Single loop. That's the beauty of it.

09 Visual Flowchart

10 Pseudocode

FUNCTION findMajorityElement(nums):
    candidate ← NULL
    count ← 0

    FOR EACH num IN nums DO:
        IF count == 0 THEN:
            candidate ← num
        END IF
        IF num == candidate THEN:
            count ← count + 1
        ELSE:
            count ← count - 1
        END IF
    END FOR

    RETURN candidate
END FUNCTION

11 Full Python Program — All 3 Methods

# ─────────────────────────────────────────────────────
# Find Majority Element — All 3 Approaches
# Author  : Siva Sankar | pro.technaga.com
# Problem : Element appearing more than n/2 times
# ─────────────────────────────────────────────────────


# ── METHOD 1: Brute Force — O(n²) Time, O(1) Space ──
def majority_brute(nums):
    n = len(nums)
    for i in range(n):
        count = 0
        for j in range(n):
            if nums[j] == nums[i]:
                count += 1
        if count > n // 2:
            return nums[i]
    return -1


# ── METHOD 2: HashMap — O(n) Time, O(n) Space ──
def majority_hashmap(nums):
    n = len(nums)
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    for num, count in freq.items():
        if count > n // 2:
            return num
    return -1


# ── METHOD 3: Boyer-Moore — O(n) Time, O(1) Space ──
def majority_boyer_moore(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate


# ── MAIN — User Input ──
if __name__ == "__main__":
    n = int(input("Enter array size: "))
    nums = list(map(int, input("Enter elements: ").split()))

    print("\n── Results ──")
    print(f"Brute Force    : {majority_brute(nums)}")
    print(f"HashMap        : {majority_hashmap(nums)}")
    print(f"Boyer-Moore    : {majority_boyer_moore(nums)}")

12 Dry Run — Step by Step

Let's trace through nums = [2, 2, 1, 1, 1, 2, 2] using Boyer-Moore.

13 Time & Space Complexity

14 Test Cases

15 Edge Cases to Watch Out For

• Single element array: Always the majority. Count becomes 1 immediately.
• All same elements: Candidate never changes. Count keeps increasing.
• No majority exists: Boyer-Moore still returns a candidate — but it could be wrong. Always verify with a second pass if the majority is NOT guaranteed.
• Negative numbers: The algorithm handles them perfectly since it only checks equality, not magnitude.
• Even-length arrays: Majority needs to appear strictly more than n/2 times, not just n/2.

16 Common Interview Questions

17 Real World Applications

18 Mistakes Beginners Make

• Forgetting to check count == 0 before updating: You must reset the candidate when count drops to zero, not after.
• Using >= instead of >: Majority means strictly more than n/2, not equal to n/2.
• Using integer division wrong: n // 2 is correct — don't forget the floor division.
• Assuming Boyer-Moore always works without verification: If majority is not guaranteed, you need a second pass to confirm.
• Not handling empty arrays: Always add a guard check if the input might be empty.

19 Conclusion

The majority element problem is a classic that every developer preparing for coding interviews should have in their toolkit. The progression from brute force → hashmap → Boyer-Moore teaches a valuable lesson: sometimes, a clever observation (the majority can't be cancelled out) leads to a dramatically better solution.

Boyer-Moore Voting Algorithm is elegant because it does something most people wouldn't expect: it solves a frequency problem without counting frequencies. If you understand why it works — not just how — you'll be able to adapt it to related problems instantly.

20 FAQ