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

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

09: 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

# ── 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.

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.

 FAQ