Backend interview prep

Start

Majority Element (LeetCode

Learn how to solve the Majority Element problem using HashMap, Sorting, and the optimal Boyer-Moore Voting Algorithm. Includes intuition, dry run, Java code, complexity analysis, edge cases, interview tips, and production applications.

Introduction

Majority Element is a frequently asked array interview problem that tests whether you can move from a straightforward counting solution to a highly optimized constant-space algorithm.

This problem is commonly associated with companies such as:

  • Amazon
  • Google
  • Microsoft
  • Meta
  • Apple
  • Adobe
  • Oracle
  • Goldman Sachs
  • JPMorgan Chase

It evaluates your understanding of:

  • Frequency counting
  • HashMap usage
  • Sorting
  • Greedy cancellation
  • Boyer-Moore Voting Algorithm
  • Time and space optimization

The most important interview insight is that the majority element appears more than half the time, allowing all other values to cancel against it.

Problem Statement

Given an integer array nums, return the element that appears more than:

⌊n / 2⌋

times.

You may assume that the majority element always exists.

Example 1

Input

nums = [3,2,3]

Output

3

Explanation:

graph TD
    n_0_0["n"] --> n_1_1["n"]
    n_0_0["n"] --> N_2_1_2["2"]
    N_3_0_1["3"] --> N_1_1_3["1"]
    n_1_1["n"] --> N_3_2_1["3"]
    n_1_1["n"] --> appears_2_2["appears"]
    N_2_1_2["2"] --> N_2_2_3["2"]
    N_2_1_2["2"] --> times_2_4["times"]
    N_3_2_1["3"] --> N_2_3_1["2"]
    N_3_2_1["3"] --> N_1_3_2["1"]

Therefore, 3 is the majority element.

Example 2

Input

nums = [2,2,1,1,1,2,2]

Output

2

Explanation:

graph TD
    n_0_0["n"] --> n_1_1["n"]
    n_0_0["n"] --> N_2_1_2["2"]
    N_7_0_1["7"] --> N_3_1_3["3"]
    n_1_1["n"] --> N_2_2_1["2"]
    n_1_1["n"] --> appears_2_2["appears"]
    N_2_1_2["2"] --> N_4_2_3["4"]
    N_2_1_2["2"] --> times_2_4["times"]
    N_2_2_1["2"] --> N_4_3_1["4"]
    N_2_2_1["2"] --> N_3_3_2["3"]

What Does Majority Mean?

A majority element appears more than half of the total array length.

For an array of size n:

Frequency > n / 2

Examples:

Array Size Majority Frequency
1 At least 1
3 At least 2
5 At least 3
6 At least 4
10 At least 6

There can be only one majority element.

Two different values cannot both appear more than n / 2 times.

Approach 1 — Brute Force

Idea

For every element:

  1. Count how many times it appears.
  2. If the count is greater than n / 2, return it.

Brute Force Flow

graph TD
    Current_Element["Current Element"] --> Scan_Entire_Array["Scan Entire Array"]
    Scan_Entire_Array["Scan Entire Array"] --> Count_Occurrences["Count Occurrences"]
    Count_Occurrences["Count Occurrences"] --> Majority["Majority?"]
    Majority["Majority?"] --> Return["Return"]

Java Code — Brute Force

public class MajorityElementBruteForce {

    public int majorityElement(int[] nums) {

        int majorityCount = nums.length / 2;

        for (int candidate : nums) {

            int count = 0;

            for (int value : nums) {

                if (value == candidate) {

                    count++;

                }

            }

            if (count > majorityCount) {

                return candidate;

            }

        }

        throw new IllegalArgumentException(
                "Majority element does not exist");

    }

}

Complexity

Complexity Value
Time O(n²)
Space O(1)

This approach is easy to understand but inefficient for large arrays.

Approach 2 — HashMap Frequency Counting

Core Idea

Store the frequency of every number in a HashMap.

For each element:

  1. Increase its count.
  2. Check whether the count is greater than n / 2.
  3. Return immediately when the majority threshold is reached.

HashMap Flow

graph TD
    Read_Number["Read Number"] --> Update_Frequency["Update Frequency"]
    Update_Frequency["Update Frequency"] --> Frequency_n_2["Frequency  n / 2?"]
    Frequency_n_2["Frequency  n / 2?"] --> Return_Number["Return Number"]

Java Code — HashMap

import java.util.HashMap;
import java.util.Map;

public class MajorityElementUsingHashMap {

    public int majorityElement(int[] nums) {

        Map<Integer, Integer> frequencies =
                new HashMap<>();

        int majorityCount = nums.length / 2;

        for (int number : nums) {

            int count = frequencies.merge(
                    number,
                    1,
                    Integer::sum);

            if (count > majorityCount) {

                return number;

            }

        }

        throw new IllegalArgumentException(
                "Majority element does not exist");

    }

}

Alternative HashMap Implementation

import java.util.HashMap;
import java.util.Map;

public class MajorityElementUsingGetOrDefault {

    public int majorityElement(int[] nums) {

        Map<Integer, Integer> frequencies =
                new HashMap<>();

        for (int number : nums) {

            frequencies.put(
                    number,
                    frequencies.getOrDefault(number, 0) + 1);

        }

        for (Map.Entry<Integer, Integer> entry
                : frequencies.entrySet()) {

            if (entry.getValue() > nums.length / 2) {

                return entry.getKey();

            }

        }

        throw new IllegalArgumentException(
                "Majority element does not exist");

    }

}

Complexity

Complexity Value
Time O(n)
Space O(n)

This is efficient but requires additional memory.

Approach 3 — Sorting

Core Idea

If the array is sorted, the majority element must occupy the middle position.

Why?

Because it appears more than half the time.

After sorting:

Majority Element

↓

Must Cross Middle Index

Therefore:

nums[nums.length / 2]

is guaranteed to be the majority element.

Example

Input:

[2,2,1,1,1,2,2]

After sorting:

[1,1,1,2,2,2,2]

Middle index:

7 / 2 = 3

Value:

nums[3] = 2

Java Code — Sorting

import java.util.Arrays;

public class MajorityElementUsingSorting {

    public int majorityElement(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length / 2];

    }

}

Complexity

Complexity Value
Time O(n log n)
Space O(log n) or implementation-dependent

This solution is concise but modifies the input array.

Approach 4 — Boyer-Moore Voting Algorithm

Core Idea

The Boyer-Moore Voting Algorithm finds the majority element in:

O(n) time

O(1) space

It works using a cancellation principle.

Maintain:

  • candidate
  • count

Rules:

  1. If count == 0, choose the current number as the new candidate.
  2. If the current number equals the candidate, increment the count.
  3. Otherwise, decrement the count.

Cancellation Intuition

Suppose the majority element is 2.

Input:

[2,2,1,1,1,2,2]

Pair each non-majority value with one majority value.

2 cancels 1

2 cancels 1

2 cancels 1

Since 2 appears more than half the time, at least one 2 must remain after all cancellations.

The final surviving candidate is the majority element.

Algorithm

graph TD
    candidate_undefined["candidate = undefined"] --> count_0["count = 0"]
    count_0["count = 0"] --> Read_Number["Read Number"]
    Read_Number["Read Number"] --> count_01["count == 0?"]
    count_01["count == 0?"] --> Set_New_Candidate["Set New Candidate"]
    Set_New_Candidate["Set New Candidate"] --> Same_as_Candidate["Same as Candidate?"]

Dry Run

Input:

[2,2,1,1,1,2,2]

Step 1

Current value:

2

Since:

count = 0

Set:

candidate = 2

Then:

count = 1

Step 2

Current value:

2

Matches candidate.

count = 2

Step 3

Current value:

1

Does not match candidate.

count = 1

Step 4

Current value:

1

Does not match candidate.

count = 0

Step 5

Current value:

1

Since count is zero:

candidate = 1

Then:

count = 1

Step 6

Current value:

2

Does not match candidate.

count = 0

Step 7

Current value:

2

Since count is zero:

candidate = 2

Then:

count = 1

Final candidate:

2

Dry Run Table

Current Value Candidate Before Count Before Action Candidate After Count After
2 — 0 Select candidate 2 1
2 2 1 Increment 2 2
1 2 2 Decrement 2 1
1 2 1 Decrement 2 0
1 2 0 Select candidate 1 1
2 1 1 Decrement 1 0
2 1 0 Select candidate 2 1

Java Code — Optimal Solution

public class MajorityElement {

    public int majorityElement(int[] nums) {

        int candidate = 0;
        int count = 0;

        for (int number : nums) {

            if (count == 0) {

                candidate = number;

            }

            if (number == candidate) {

                count++;

            } else {

                count--;

            }

        }

        return candidate;

    }

}

Cleaner Java Implementation

public class Solution {

    public int majorityElement(int[] nums) {

        int candidate = nums[0];
        int count = 0;

        for (int number : nums) {

            if (count == 0) {

                candidate = number;

            }

            count += number == candidate ? 1 : -1;

        }

        return candidate;

    }

}

Complexity Analysis

Complexity Value
Time O(n)
Space O(1)

This is the optimal solution.

Why Boyer-Moore Works

Assume the majority element is M.

Because M appears more than n / 2 times:

Frequency(M) > Frequency(all other elements combined)

Every time a different value appears, it cancels one occurrence of the current candidate.

Even after all possible cancellations, the majority element still has unmatched occurrences.

Therefore, the final candidate must be the majority element.

Formal Intuition

Let:

m = count of majority element

o = count of all other elements

Since:

m > o

After pairing each non-majority element with one majority element:

m - o > 0

At least one majority element remains.

Is Verification Required?

For LeetCode #169, verification is not required because the problem guarantees that the majority element exists.

However, in a general production scenario, the candidate should be verified.

Boyer-Moore with Verification

public class MajorityElementWithValidation {

    public int majorityElement(int[] nums) {

        int candidate = 0;
        int count = 0;

        for (int number : nums) {

            if (count == 0) {

                candidate = number;

            }

            count += number == candidate ? 1 : -1;

        }

        int frequency = 0;

        for (int number : nums) {

            if (number == candidate) {

                frequency++;

            }

        }

        if (frequency <= nums.length / 2) {

            throw new IllegalArgumentException(
                    "Majority element does not exist");

        }

        return candidate;

    }

}

Complexity remains:

Time: O(n)

Space: O(1)

The array is traversed twice.

Edge Cases

Single Element

Input

[5]

Output

5

A single element is automatically the majority.

All Elements Are the Same

Input

[4,4,4,4]

Output

4

Majority Appears at the Beginning

Input

[3,3,3,1,2]

Output

3

Majority Appears at the End

Input

[1,2,4,4,4]

Output

4

Negative Numbers

Input

[-1,-1,-1,2,3]

Output

-1

Array with Two Values

Input

[7,7,2]

Output

7

Comparison of Approaches

Approach Time Space Modifies Input Recommended
Brute Force O(n²) O(1) No No
HashMap O(n) O(n) No Good
Sorting O(n log n) Sorting-dependent Yes Acceptable
Boyer-Moore O(n) O(1) No Best

Common Interview Mistakes

Mistake 1 — Returning the Most Recent Candidate Without Understanding the Guarantee

Boyer-Moore returns a valid majority only when a majority element is guaranteed or verified afterward.

Mistake 2 — Using >= n / 2

The majority condition is:

count > n / 2

not:

count >= n / 2

For example, in an array of size 4, a value appearing 2 times is not a majority.

Mistake 3 — Confusing Majority with Mode

The mode is the most frequent element.

A majority must appear more than half the time.

Example:

[1,1,2,2,3]

Both 1 and 2 are modes, but no majority exists.

Mistake 4 — Forgetting Sorting Modifies the Input

Arrays.sort(nums);

changes the original array.

Mention this trade-off during interviews.

Mistake 5 — Using a HashMap Without Discussing Space

The HashMap solution is linear time but requires up to:

O(n)

extra space.

Mistake 6 — Incorrect Candidate Reset

The candidate must be reset only when:

count == 0

Production Applications

The majority-element pattern appears in:

  • Election result processing
  • Distributed consensus analysis
  • Most common event detection
  • Feature flag adoption tracking
  • Customer behavior analysis
  • Log event classification
  • Fraud signal aggregation
  • Dominant category detection
  • Monitoring alert analysis
  • Telemetry processing

Real-World Example — Election Voting

Suppose votes are represented as:

[A, A, B, A, C, A, A]

Candidate A appears:

5 times out of 7

Since:

5 > 7 / 2

A has an absolute majority.

Boyer-Moore can identify the majority candidate using constant extra memory.

Real-World Example — Distributed Systems

Suppose several nodes report a configuration version:

[v3, v3, v2, v3, v1, v3, v3]

If one version appears on more than half the nodes, it may be treated as the dominant cluster state.

The same cancellation principle can identify the candidate efficiently.

However, real distributed consensus requires stronger correctness guarantees than simple majority counting.

Follow-Up Question 1 — What If Majority Is Not Guaranteed?

Use Boyer-Moore to identify a candidate.

Then count its frequency in a second pass.

Return the candidate only when:

frequency > n / 2

Follow-Up Question 2 — Find Elements Appearing More Than n/3 Times

This becomes LeetCode #229 — Majority Element II.

There can be at most two such elements.

Use an extended Boyer-Moore algorithm with:

  • Two candidates
  • Two counters
  • Verification pass

Follow-Up Question 3 — Find Elements Appearing More Than n/k Times

There can be at most:

k - 1

such elements.

A generalized Boyer-Moore algorithm maintains up to k - 1 candidates.

Follow-Up Question 4 — What If the Input Is a Stream?

If the majority element is guaranteed, Boyer-Moore works well for streaming data because it requires only:

O(1)

memory.

If verification is required and the stream cannot be replayed, additional storage or an external counting system may be necessary.

Follow-Up Question 5 — Can Sorting Be Used?

Yes.

After sorting, return:

nums[nums.length / 2];

But sorting requires:

O(n log n)

time and modifies the array.

Follow-Up Question 6 — Can HashMap Be Better Than Boyer-Moore?

HashMap is easier to understand and can provide:

  • Exact frequencies
  • Support for no-majority scenarios
  • Frequency reporting for every value

Boyer-Moore is better when:

  • Only the majority candidate is needed
  • Memory must remain constant
  • Majority existence is guaranteed

Interview Explanation

A strong interview explanation could be:

The optimal solution is the Boyer-Moore Voting Algorithm. I maintain a candidate and a counter. When the counter becomes zero, I select the current element as the new candidate. Matching values increase the counter, while different values decrease it. Since the majority element appears more times than all other elements combined, it cannot be completely canceled and remains as the final candidate. This gives O(n) time and O(1) extra space.

Interview Tips

Interviewers commonly ask:

  • What is the difference between majority and most frequent?
  • Why does Boyer-Moore work?
  • Why can there be only one majority element?
  • Is a verification pass required?
  • What happens if majority is not guaranteed?
  • How would you solve the n / 3 version?
  • Why is sorting valid?
  • What is the HashMap space complexity?
  • Can the algorithm process streaming input?
  • Explain the cancellation logic with a dry run.

Always explain the cancellation intuition before writing the code.

Unit Tests

import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

class MajorityElementTest {

    private final MajorityElement solution =
            new MajorityElement();

    @Test
    void shouldFindMajorityInSmallArray() {

        int[] nums = {3, 2, 3};

        assertEquals(
                3,
                solution.majorityElement(nums));

    }

    @Test
    void shouldFindMajorityInLargerArray() {

        int[] nums = {2, 2, 1, 1, 1, 2, 2};

        assertEquals(
                2,
                solution.majorityElement(nums));

    }

    @Test
    void shouldHandleSingleElement() {

        int[] nums = {5};

        assertEquals(
                5,
                solution.majorityElement(nums));

    }

    @Test
    void shouldHandleNegativeValues() {

        int[] nums = {-1, -1, -1, 2, 3};

        assertEquals(
                -1,
                solution.majorityElement(nums));

    }

    @Test
    void shouldHandleAllSameValues() {

        int[] nums = {4, 4, 4, 4};

        assertEquals(
                4,
                solution.majorityElement(nums));

    }

}

Summary

The Majority Element problem demonstrates how a counting problem can be optimized from a frequency map to a constant-space voting algorithm.

The HashMap solution is intuitive and runs in linear time but requires additional memory.

Sorting provides a concise solution but costs O(n log n) time and modifies the array.

The Boyer-Moore Voting Algorithm is optimal because it uses the cancellation property of the majority element.

Optimal complexity:

Time: O(n)

Space: O(1)

Key Takeaways

  • A majority element appears more than n / 2 times.
  • There can be only one majority element.
  • Brute force requires O(n²) time.
  • HashMap provides O(n) time and O(n) space.
  • Sorting places the majority element at the middle index.
  • Boyer-Moore uses candidate cancellation.
  • The majority element survives all cancellations.
  • The optimal algorithm runs in O(n) time.
  • The optimal algorithm uses O(1) extra space.
  • Verify the candidate when majority existence is not guaranteed.
  • Understand the difference between majority and mode.
  • Practice the n / 3 follow-up problem.