Free lesson · DSA Mastery - Interview Prep, End to End

Majority Element

Medium8 min readdsaarrays

Majority Element

Majority Element is famous for one reason: the Boyer-Moore voting algorithm, which solves it in O(n) time and O(1) space. The algorithm is short, surprising, and produces correct results through a mechanism that doesn't immediately look like it should work. Once you see why it works, it's hard to unsee - and the technique generalizes to a whole family of problems.

This is one of the most-asked array problems in interviews because the Boyer-Moore algorithm is a perfect example of "the clever solution beats the obvious one." Hash map: O(n) time, O(n) space. Sort: O(n log n) time, O(1) space. Boyer-Moore: O(n) time, O(1) space - strictly better than both.

The Problem

Given an array nums of size n, return the majority element - the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input:  nums = [3, 2, 3]
Output: 3

Example 2:

Input:  nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

Explanation: 2 appears 4 times, which is more than 7/2 = 3.

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

Follow-up: Could you solve the problem in linear time and O(1) space?

Approach

Three approaches worth knowing, in order of cleverness.

Approach 1: Hash Map (O(n) time, O(n) space)

Count occurrences in a hash map. Return whichever element has count > n / 2. Straightforward but uses extra space.

Approach 2: Sort (O(n log n) time, O(1) space)

Sort the array. The majority element appears more than n / 2 times, so it must occupy the middle position nums[n / 2]. Return that element. Slower than approach 1 but constant space.

Approach 3: Boyer-Moore Voting (O(n) time, O(1) space)

This is the algorithm worth learning. The idea: maintain a candidate and a counter.

• For each element, if the counter is 0, set this element as the new candidate.
• If the element matches the candidate, increment the counter.
• Otherwise, decrement the counter.

After the scan, the candidate is the majority element.

The intuition: think of the algorithm as pairing up different elements and canceling them. Each "candidate vs non-candidate" matchup cancels both. Since the majority element appears more than n / 2 times, it has more votes than all other elements combined. After all the cancellations, the majority element is the one left standing.

graph TD
    A["candidate = null<br/>count = 0"] --> B["For each num"]
    B --> C{"count == 0?"}
    C -->|Yes| D["candidate = num"]
    C -->|No| E["skip setting candidate"]
    D --> F{"num == candidate?"}
    E --> F
    F -->|Yes| G["count++"]
    F -->|No| H["count--"]
    G --> I{"More?"}
    H --> I
    I -->|Yes| B
    I -->|No| J["Return candidate"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the Boyer-Moore voting algorithm. We track a candidate and a count. For each element, if count is zero we set the element as the new candidate. Then we check if the element matches the candidate. If yes, we increment count. If no, we decrement count. After the scan, the candidate is the majority element.

Code Implementation

public static int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }
    
    return candidate;
}

// Usage:
// int[] nums = {2, 2, 1, 1, 1, 2, 2};
// System.out.println(majorityElement(nums));  // 2

This Java code implements the Boyer-Moore voting algorithm. We track a candidate and a count. For each element, if count is zero we set candidate to the element. Then we increment or decrement count based on whether the element matches the candidate. After the loop, candidate holds the majority element.

The algorithm is six lines. It's worth pausing to appreciate that - it solves a non-trivial problem in O(1) space with no tricks like bit packing or array mutation.

For interview safety, you should typically verify the candidate with a second pass when the problem doesn't guarantee that a majority exists. But this problem guarantees it, so the single pass is sufficient.

Walkthrough

Let's trace on nums = [2, 2, 1, 1, 1, 2, 2].

Initial: candidate = 0, count = 0

num=2: count==0, candidate=2. 2==2, count=1.
       State: candidate=2, count=1
num=2: count!=0. 2==2, count=2.
       State: candidate=2, count=2
num=1: count!=0. 1!=2, count=1.
       State: candidate=2, count=1
num=1: count!=0. 1!=2, count=0.
       State: candidate=2, count=0
num=1: count==0, candidate=1. 1==1, count=1.
       State: candidate=1, count=1
num=2: count!=0. 2!=1, count=0.
       State: candidate=1, count=0
num=2: count==0, candidate=2. 2==2, count=1.
       State: candidate=2, count=1

Return candidate = 2.

Result: 2. And 2 is correct - it appears 4 times in an array of length 7, which is more than 7/2 = 3.

Notice how the candidate changed multiple times during the scan. The first half of the array gave candidate 2, then 1 briefly took over, then 2 took back over at the end. Even with this back-and-forth, the algorithm correctly identifies 2 as the majority.

Let's also trace [3, 2, 3]:

Initial: candidate=0, count=0

num=3: count==0, candidate=3. 3==3, count=1.
num=2: 2!=3, count=0.
num=3: count==0, candidate=3. 3==3, count=1.

Return candidate = 3.

Result: 3. Correct.

Complexity Analysis

Why Boyer-Moore Works

The proof has two parts:

Part 1: The majority element survives. Pair up each occurrence of the majority element with one occurrence of a non-majority element. After this pairing, since the majority appears more than n/2 times, there are leftover majority occurrences but no leftover non-majority occurrences. The leftover majority votes ensure the candidate at the end is the majority.

Part 2: The algorithm correctly tracks "majority - others" effectively. Each iteration either votes "for" (count++) or "against" (count--) the current candidate. The candidate can change, but the algorithm's invariant is that count represents the net votes for the current candidate in the suffix since the last reset. The majority element accumulates more votes than it loses, so it ends as the final candidate.

More formally: consider the algorithm as running through "elections" separated by resets. In each election, the candidate either wins (positive count at the end) or ties (count reaches zero and a new candidate takes over). In the final election, the majority element wins because there are not enough non-majority elements left to tie it.

Why It's Better Than the Alternatives

• Hash map approach: O(n) time, O(n) space. Loses on space.
• Sort approach: O(n log n) time, O(1) space (in-place sort). Loses on time.
• Boyer-Moore: O(n) time, O(1) space. Beats both.

For a 1 million element array, Boyer-Moore is faster than sort by a factor of about 20 (the log n factor), and uses zero auxiliary memory versus the hash map's million-entry table.

When Verification Is Needed

Boyer-Moore returns a candidate, not necessarily the majority. If no majority exists, the candidate could be any frequent element - or even an arbitrary one.

When the problem guarantees a majority exists (as in this problem), the candidate is correct without verification. When no such guarantee exists, run a second pass to verify the candidate's count > n/2 before returning it.

Variations & Follow-ups

What if the problem doesn't guarantee a majority?

Add a verification pass:

public static Integer majorityElementOrNull(int[] nums) {
    // First pass: find candidate
    int candidate = 0, count = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    
    // Second pass: verify
    int actualCount = 0;
    for (int num : nums) {
        if (num == candidate) actualCount++;
    }
    
    return actualCount > nums.length / 2 ? candidate : null;
}

Two passes, still O(n) time and O(1) space. The verification is essential when no majority is guaranteed.

What if you need elements appearing more than n/3 times?

That's Majority Element II (the next problem). The Boyer-Moore generalization is beautiful: track two candidates instead of one. At most two elements can each appear more than n/3 times.

The pattern extends: to find elements appearing more than n/k times, track k - 1 candidates. The space is O(k), and the algorithm is O(nk). For small k, this is excellent.

What if you need the kth most common element?

The Boyer-Moore approach doesn't generalize that far. For "find the kth most common," use a hash map + heap approach. We'll see this pattern in Section 25 (Heaps).

Why does setting the candidate happen before the increment check?

The order matters. We set the candidate when count == 0, then we check if the current element matches the (now possibly new) candidate, then we increment or decrement count.

If the count just reset to 0 and the new candidate is the current element, the comparison succeeds and count becomes 1. This is what we want - the algorithm starts a fresh "election" with the current element as the candidate.

What about edge cases?

• Single element: count==0, candidate set, count incremented to 1. Returns that element. Correct (a single-element array trivially has that element as majority).
• All identical: Candidate set to that element. Count grows linearly. Returns that element. Correct.
• Two elements, both equal: Same as all identical. Correct.
• Two elements, different: The problem says majority always exists, so this won't happen. But the algorithm would return the first element, which would be wrong (no majority).
• Mixed with the majority barely above n/2: The Boyer-Moore math works for any majority. As long as the count of majority occurrences is greater than n/2, the algorithm returns it.

Common Interview Pitfalls

• Setting the candidate in the wrong place. Setting candidate after the comparison would skip the new candidate's vote. Always set candidate first when count == 0, then compare.
• Returning the count instead of the candidate. A simple typo that makes the answer wildly wrong.
• Not handling count overflow. For very large arrays, count can grow large, but it fits comfortably in an int for any reasonable n.
• Verifying when not needed. This problem guarantees a majority, so verification is wasted work. Read the problem constraints carefully before adding extra passes.
• Forgetting that the candidate can change. Junior candidates sometimes try to "lock in" the candidate after seeing a certain count. Don't. Let the algorithm run to completion.

Why This Problem Matters

Boyer-Moore is one of the most beautiful algorithms in this course. It's:

• Simple (6 lines of code)
• Optimal (O(n) time, O(1) space)
• Surprising (the proof isn't obvious)
• Generalizable (extends to n/k majority)

It's also a great signal for interviewers. If a candidate proposes the hash map or sort approach, that's reasonable but not optimal. If they propose Boyer-Moore, that signals "this person has studied algorithms beyond the obvious." It's one of those problems where knowing the right technique is a real advantage.

The next chapter, Majority Element II, generalizes Boyer-Moore to elements appearing more than n/3 times. The generalization is even more interesting than the original.

Back to DSA Mastery - Interview Prep, End to End