Majority Element

Problem Statement

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.

What to notice first

• The problem guarantees a majority element exists, so you never need to handle the “not found” case.
• Because the majority element appears more than n/2 times, there can be at most one such element.
• The Boyer-Moore algorithm exploits this uniqueness guarantee to solve the problem in O(1) space.

Examples

Input	Output	Explanation
[3, 2, 3]	3	3 appears 2 times out of 3 (> 1.5)
[2, 2, 1, 1, 1, 2, 2]	2	2 appears 4 times out of 7 (> 3.5)

Constraints

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• A majority element always exists.

Real-World Applications

Where this pattern appears

• Distributed voting systems — identify the candidate that more than half of nodes agree on.
• Fault-tolerant consensus — in a cluster of servers, find the value that a majority of nodes have committed.
• Dominant colour detection — find the colour that covers more than half the pixels in a compressed image tile.
• Stream analytics — identify the event type that dominates a data stream without storing the whole stream.

Complexity Comparison

Approach	Time	Space	Best When
Hash Map	O(n)	O(n)	Straightforward to understand; easy to adapt to count all elements
Boyer-Moore	O(n)	O(1)	Memory is critical; the classic interview-worthy approach

Which approach should you learn first?

• Learn Hash Map first to build intuition — count everything, return the one that exceeds the threshold.
• Learn Boyer-Moore for interviews — O(1) space is the follow-up every interviewer expects.

Interview Favourite

Boyer-Moore

O(n) time · O(1) space

Easy to Understand

Hash Map

O(n) time · O(n) space

Approach 1: Hash Map

✓ Simple

Count every element’s frequency in a hash map, then return the first element whose count exceeds n / 2. Because the majority element is guaranteed to exist, the loop always finds one.

⏱ Time O(n) Single pass 💾 Space O(n) Map stores up to n elements

Step-by-step Example

Input: [2, 2, 1, 1, 1, 2, 2], threshold = 3

num	count after	> threshold?
2	{2:1}	No
2	{2:2}	No
1	{2:2, 1:1}	No
1	{2:2, 1:2}	No
1	{2:2, 1:3}	No
2	{2:3, 1:3}	No
2	{2:4, 1:3}	Yes → return 2

Pseudocode

function majorityElement(nums):
    threshold = len(nums) // 2
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > threshold:
            return num

Solution Code

Python

majority_element_hash_map.py

from typing import List


def majority_element(nums: List[int]) -> int:
    counts = {}
    threshold = len(nums) // 2
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > threshold:
            return num
    return nums[0]

C++

majority_element_hash_map.cpp

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int threshold = nums.size() / 2;
        for (int num : nums) {
            counts[num]++;
            if (counts[num] > threshold) return num;
        }
        return nums[0];
    }
};

Java

majority_element_hash_map.java

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

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        int threshold = nums.length / 2;
        for (int num : nums) {
            int next = counts.getOrDefault(num, 0) + 1;
            counts.put(num, next);
            if (next > threshold) return num;
        }
        return nums[0];
    }
}

JavaScript

majority_element_hash_map.js

function majorityElement(nums) {
    const counts = new Map();
    const threshold = Math.floor(nums.length / 2);
    for (const num of nums) {
        const next = (counts.get(num) || 0) + 1;
        counts.set(num, next);
        if (next > threshold) return num;
    }
    return nums[0];
}

Rust

majority_element_hash_map.rs

use std::collections::HashMap;

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut counts = HashMap::new();
        let threshold = nums.len() / 2;
        for num in nums {
            let next = counts.entry(num).or_insert(0);
            *next += 1;
            if *next > threshold as i32 {
                return num;
            }
        }
        0
    }
}

Go

majority_element_hash_map.go

func majorityElement(nums []int) int {
    counts := map[int]int{}
    threshold := len(nums) / 2
    for _, num := range nums {
        counts[num]++
        if counts[num] > threshold {
            return num
        }
    }
    return nums[0]
}

Approach 2: Boyer-Moore Voting

🎯 Interview Favourite

Maintain a candidate and a count. When count drops to zero, the current element becomes the new candidate. When the current element matches the candidate, increment; when it differs, decrement. The majority element’s count can never be fully cancelled out, so it always survives as the final candidate.

Mental model: think of it as a battle. Every non-candidate element cancels one candidate vote. Because the majority element has more votes than all others combined, it wins the war even if it loses individual battles.

⏱ Time O(n) Single pass 💾 Space O(1) Two variables only

Step-by-step Example

Input: [3, 2, 3]

i	num	Action	candidate	count
0	3	Initialise	3	1
1	2	2 ≠ 3, decrement	3	0
2	3	count=0, new candidate	3	1
—	—	Return 3	—	—

Input: [2, 2, 1, 1, 1, 2, 2]

i	num	candidate	count
0	2	2	1
1	2	2	2
2	1	2	1
3	1	2	0
4	1	1	1
5	2	1	0
6	2	2	1
—	—	Return 2	—

Animated walkthrough

How Boyer-Moore voting finds the majority element

Use Next or Autoplay to watch the candidate and count change as each element either reinforces or challenges the current front-runner.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function majorityElement(nums):
    candidate, count = nums[0], 1
    for num in nums[1:]:
        if count == 0:
            candidate, count = num, 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

Solution Code

Python

majority_element_boyer_moore.py

from typing import List


def majority_element(nums: List[int]) -> int:
    candidate, count = nums[0], 1
    for num in nums[1:]:
        if count == 0:
            candidate, count = num, 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    return candidate


print(majority_element([3, 2, 3]))              # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 2

C++

majority_element_boyer_moore.cpp

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < (int)nums.size(); i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
};

Java

majority_element_boyer_moore.java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

JavaScript

majority_element_boyer_moore.js

function majorityElement(nums) {
    let candidate = nums[0], count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] === candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

Rust

majority_element_boyer_moore.rs

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut candidate = nums[0];
        let mut count = 1i32;
        for &num in &nums[1..] {
            if count == 0 {
                candidate = num;
                count = 1;
            } else if num == candidate {
                count += 1;
            } else {
                count -= 1;
            }
        }
        candidate
    }
}

Go

majority_element_boyer_moore.go

package golang
func majorityElement(nums []int) int {
  candidate, count := nums[0], 1
  for _, num := range nums[1:] {
    if count == 0 {
      candidate, count = num, 1
    } else if num == candidate {
      count++
    } else {
      count--
    }



}  return candidate  }

Watch for these pitfalls

• Boyer-Moore only works when a majority element is guaranteed to exist. Without that guarantee you must do a second pass to verify the candidate.
• Do not confuse majority (> n/2) with plurality (most frequent) — they are different problems.
• The hash map approach can be adapted to find the top-k frequent elements; Boyer-Moore cannot without modification.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

majority_element_space_optimized.py

"""
Solution for Majority Element
"""

def solve():
    """Implementation for approach 3 of Majority Element"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

majority_element_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Majority Element
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

MajorityElementSpaceOptimized.java

/**
 * Solution for Majority Element
 * Approach 3
 */
public class MajorityElementSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

majority_element_space_optimized.js

/**
 * Solution for Majority Element
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

majority_element_space_optimized.rs

/// Solution for Majority Element
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

majority_element_space_optimized.go

package main

import "fmt"

// Solution for Majority Element
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum Easy #1
• Contains Duplicate Easy #217
• Majority Element II ↗ Medium #229
• Top K Frequent Elements ↗ Medium #347

Interview Tips

Key trade-offs to discuss

• Why Boyer-Moore? It is the only O(n) time, O(1) space solution — a classic algorithm worth knowing by name.
• Why does it work? The guarantee that the majority element appears more than n/2 times means its votes can never all be cancelled by the minority.
• What if the majority element is not guaranteed? Add a second pass to count the candidate’s actual occurrences and verify it exceeds n/2.
• Follow-up — Majority Element II (> n/3)? Boyer-Moore generalises: maintain two candidates and two counts for finding elements appearing more than n/3 times.

← Previous
#167 Two Sum II – Input Array Is Sorted Next
#172 Factorial Trailing Zeroes →