Log inSign up
easyLeetCodeNot Started

Majority Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

Example 1 · Standard Odd-Length Array:

Input: nums = [3, 2, 3]
Output: 3
Explanation: The array length n = 3. ⌊3 / 2⌋ = 1. Element 3 appears 2 times, which is > 1. Thus, 3 is the majority element.

Example 2 · Even-Length Array with Multiple Distractors:

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: The array length n = 7. ⌊7 / 2⌋ = 3. Element 2 appears 4 times, which is > 3. Element 1 appears 3 times (<= 3). Output is 2.

Example 3 · Single Element Array:

Input: nums = [1]
Output: 1
Explanation: Array length n = 1. ⌊1 / 2⌋ = 0. Element 1 appears 1 time (> 0), so the majority element is 1.

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array traversal and basic counting
  • Hash Map frequency counting
  • Understanding the mathematical definition of majority (> 50%)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the cancellation principle behind the Boyer-Moore Voting Algorithm.
  • Derive the mathematical proof of why the majority element always survives.
  • Implement the optimal single-pass O(N) time and O(1) space algorithm.
  • Know how to adapt the algorithm when majority element existence is NOT guaranteed.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks for an element that occurs strictly more than N/2 times.
  • Guaranteed existence of a dominant element.
  • The dominant element outnumbers all competing elements combined.

Algorithmic Decision Tree:

  • If extra memory is allowed: Hash Map gives O(N) time and O(N) space.
  • If O(1) space is required: Boyer-Moore Voting Algorithm finds the candidate in O(N) time and O(1) space.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Nested Frequency Count

Intuition

For each unique element, count its occurrences across the entire array using a nested loop. Return the element if its count exceeds n / 2.

Algorithm

  1. Let majorityThreshold = n / 2.
  2. Loop i from 0 to n - 1:
  3. Initialize count = 0.
  4. Loop j from 0 to n - 1:
  5. If nums[j] == nums[i], increment count.
  6. If count > majorityThreshold, return nums[i].
  7. Return -1 (fallback).

Brute Force Candidate Count Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 2, 1, 1, 1, 2, 2]
Current operationSTEP 1 OF 6
Phase 1 — Count occurrences of 2 across the entire array: Step 1: Pick candidate nums[0] = 2
Visual state
Values and pointers at this exact step
array
S
2
2
1
1
1
2
2
0
↑ Candidate = 2
1
2
3
4
5
6
Variables at this step
Candidate
2
Threshold
> 3
Check / comparison
Target threshold: > 7 / 2 = 3.5 (need at least 4 occurrences).
Decision / next transition
Count occurrences of 2 across the entire array.
Why this step matters

Phase 1 — Count occurrences of 2 across the entire array: Step 1: Pick candidate nums[0] = 2. We need > 3 occurrences to be the majority.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: Quadratic nested counting
6int majorityElement(vector<int>& nums) {
7 int n = nums.size();
8 int majorityThreshold = n / 2;
9
10 for (int i = 0; i < n; i++) {
11 int count = 0;
12 for (int j = 0; j < n; j++) {
13 if (nums[j] == nums[i]) {
14 count++;
15 }
16 }
17 if (count > majorityThreshold) {
18 return nums[i];
19 }
20 }
21
22 return -1;
23}
24
25int main() {
26 vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
27 cout << "Output: " << majorityElement(nums) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Nested Frequency Count.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Nested Frequency Count.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Hash Map Frequency Table

Intuition

Count the frequency of each number using a hash table in a single pass. Return the element whose count exceeds n / 2.

Algorithm

  1. Initialize an empty hash map freq.
  2. Let majorityThreshold = n / 2.
  3. For each number num in nums:
  4. freq[num] = freq.get(num, 0) + 1.
  5. If freq[num] > majorityThreshold, return num.
  6. Return -1.

Hash Map Frequency Accumulator Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 2, 1, 1, 1, 2, 2]
Current operationSTEP 1 OF 6
Phase 1 — map = { 2: 2 }: Step 1: Process indices 0 and 1
Visual state
Values and pointers at this exact step
array
S
2
2
1
1
1
2
2
0
↑ Scan 2s
1
2
3
4
5
6
Variables at this step
map
{ 2: 2 }
Check / comparison
Count frequency of 2: count[2] = 2.
Decision / next transition
map = { 2: 2 }.
Why this step matters

Phase 1 — map = { 2: 2 }: Step 1: Process indices 0 and 1. count[2] = 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6// Better: Hash Map frequency counting in O(N) time and O(N) space
7int majorityElement(vector<int>& nums) {
8 unordered_map<int, int> freq;
9 int threshold = nums.size() / 2;
10
11 for (int num : nums) {
12 freq[num]++;
13 if (freq[num] > threshold) {
14 return num;
15 }
16 }
17
18 return -1;
19}
20
21int main() {
22 vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
23 cout << "Output: " << majorityElement(nums) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Hash Map Frequency Table.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Hash Map Frequency Table.

3. Optimal — Boyer-Moore Voting Algorithm (O(1) Space)

Intuition

Maintain a candidate and a counter. Pair off and cancel opposing elements. The majority element is guaranteed to survive.

Algorithm

  1. Initialize candidate = 0 and count = 0.
  2. For each number num in nums:
  3. If count == 0:
  4. candidate = num.
  5. count = 1.
  6. Else if num == candidate:
  7. count++.
  8. Else:
  9. count--.
  10. Return candidate.

Boyer-Moore Voting Algorithm State Machine Trace

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [2, 2, 1, 1, 1, 2, 2]
Current operationSTEP 1 OF 8
Phase 1 — candidate = 2, count = 1: Step 1 (Idx 0): Initial count is 0
Visual state
Values and pointers at this exact step
array
S
2
2
1
1
1
2
2
0
↑ i=0 (Candidate)
1
2
3
4
5
6
Variables at this step
Candidate
2
Count
1
Check / comparison
count == 0. Pick candidate = nums[0] (2). count = 1.
Decision / next transition
candidate = 2, count = 1.
Why this step matters

Phase 1 — candidate = 2, count = 1: Step 1 (Idx 0): Initial count is 0. Set candidate to 2, increment count to 1.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal: Boyer-Moore Voting Algorithm in O(N) time and O(1) space
6int majorityElement(vector<int>& nums) {
7 int candidate = 0;
8 int count = 0;
9
10 for (int num : nums) {
11 if (count == 0) {
12 candidate = num;
13 count = 1;
14 } else if (num == candidate) {
15 count++;
16 } else {
17 count--;
18 }
19 }
20
21 return candidate;
22}
23
24int main() {
25 vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
26 cout << "Output: " << majorityElement(nums) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Boyer-Moore Voting Algorithm (O(1) Space).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Boyer-Moore Voting Algorithm (O(1) Space).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Count)O(N²)O(1)Simple nested loop logic.Baseline only.
2.Hash Map FrequencyO(N)O(N)Intuitive, works even when majority element does not exist.Good working solution; expect interviewer to ask for O(1) space.
3.Boyer-Moore VotingOptimalO(N)O(1)Optimal linear time, strictly O(1) auxiliary memory.Gold standard optimal interview solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array with a Single Element — Input: nums = [1], Expected: 1 — With N = 1, threshold is 0. Element 1 appears once (> 0). Initial candidate assignment returns 1 immediately.
  • All Elements Identical — Input: nums = [5, 5, 5, 5, 5], Expected: 5 — Count increments to 5 without any cancellations; returns 5.
  • Majority Element Alternating with Distractors — Input: nums = [1, 2, 1, 3, 1, 4, 1], Expected: 1 — Element 1 appears 4 out of 7 times. Alternating elements continuously trigger decrements and resets, but 1 still wins the final count.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarification — Ask: 'Is it guaranteed that a majority element always exists?' If yes, Boyer-Moore needs only 1 pass. If no, mention you need a 2nd verification pass.
  2. Explain the Aha! Moment — Explain the voting algorithm as an election where votes for candidates cancel out opposing votes. Since the majority holds > 50% of votes, they always win.
  3. Follow-up: Majority Element II — Be prepared for the generalized follow-up: 'Find all elements that appear more than ⌊N / 3⌋ times' (Boyer-Moore with 2 candidates and 2 counters).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Majority Element?

2.Why is the brute force approach suboptimal for large inputs in Majority Element?

3.Which data structure or technique enables the optimal solution for Majority Element?

Back to DSA Sheet