Majority Element

Tags

Majority Element

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of positive integers, find the majority element — the element that appears more than half the time. It is guaranteed that a majority element always exists in the input.

Intuition

The Boyer-Moore Voting Algorithm treats the problem like an election. It maintains a candidate and a counter. When the counter drops to zero, the current element becomes the new candidate. The key insight is that the majority element, appearing more than n/2 times, can never be fully "voted out" by all other elements combined.

Approach

  1. Initialize candidate = array[0] and count = 0.
  2. Iterate through each element:
    • If count == 0, set candidate = element.
    • If element == candidate, increment count.
    • Otherwise, decrement count.
  3. Return candidate (guaranteed to be the majority element since one is guaranteed to exist).

Pseudocode

function majorityElement(array):
    candidate = array[0]
    count = 0

    for element in array:
        if count == 0:
            candidate = element
        if element == candidate:
            count += 1
        else:
            count -= 1

    return candidate

Time & Space Complexity

  • Time: O(n) — single pass through the array.
  • Space: O(1) — only two variables regardless of input size.

Key Insights

  • Boyer-Moore works because the majority element has more than n/2 occurrences. Every time it gets "cancelled" by a different element, there are still enough remaining majority elements to win.
  • If the problem does not guarantee a majority element exists, a second verification pass is needed to confirm the candidate actually exceeds n/2 occurrences.
  • The algorithm does not require sorting or extra data structures, making it optimal in both time and space.
  • The order of checking matters: set the candidate when count is zero before comparing.

Edge Cases

  • Array of length 1: the single element is the majority.
  • All elements are the same: that element is trivially the majority.
  • Majority element appears exactly floor(n/2) + 1 times: the minimum count to be a majority.
  • The majority element is at the end of the array: Boyer-Moore still identifies it because earlier cancellations reduce the count of non-majority elements.

Linked mentions