Majority Element
Java coding interview problem for Array Logic: Majority Element.
Finding the majority element is one of the most important array problems in coding interviews.
This problem introduces powerful concepts:
- Frequency counting
- Hashing
- Sorting
- Greedy algorithms
- Boyer-Moore Voting Algorithm
- Space optimization
It is a foundation for many advanced problems:
- Majority Element II
- Frequency analysis
- Voting algorithms
- Data stream processing
What is Majority Element?
A majority element is an element that appears more than half of the array size.
Mathematically:
count(element) > n / 2
where:
n = length of array
Example 1
Input:
nums = [3,2,3]
Array length:
n = 3
Frequency:
3 appears 2 times
Condition:
2 > 3/2
True.
Output:
3
Example 2
Input:
nums = [2,2,1,1,1,2,2]
Frequency:
2 → 4 times
1 → 3 times
Array length:
7
Majority condition:
4 > 7/2
True.
Output:
2
Example 3
Input:
nums = [1]
Output:
1
Understanding Majority Element
Consider:
[2,2,1,2,3,2,2]
Count:
2 → 5 times
1 → 1 time
3 → 1 time
Array length:
7
Majority threshold:
7 / 2 = 3
Need:
count > 3
Since:
5 > 3
Majority element:
2
Why is This Question Asked in Interviews?
Interviewers ask this problem because it tests:
1. Frequency Counting
Can you identify the most frequent element?
2. Optimization
Can you improve:
O(n²)
to:
O(n)
3. Memory Management
Can you solve without extra storage?
4. Algorithm Knowledge
Do you know:
Boyer-Moore Voting Algorithm
Real-World Applications
Voting Systems
A candidate receiving more than 50% votes becomes the winner.
Example:
Votes:
[A,B,A,A,C,A]
Count:
A → 4
B → 1
C → 1
Winner:
A
Distributed Systems
Finding the dominant value in distributed events.
Example:
Logs:
SUCCESS
FAILED
SUCCESS
SUCCESS
Majority status:
SUCCESS
Data Analytics
Finding the most dominant category.
Example:
User actions:
BUY
VIEW
BUY
BUY
Majority action:
BUY
Network Monitoring
Detecting dominant traffic patterns.
Problem Statement
Given an integer array:
nums
find the element that appears more than:
n / 2
times.
Assume that the majority element always exists.
Constraints
Example:
1 <= nums.length <= 50000
Values:
-10^9 <= nums[i] <= 10^9
Understanding Frequency Logic
Example:
Input:
[3,3,4,2,3,3,5]
Create frequency table:
| Number | Count |
|---|---|
| 2 | 1 |
| 3 | 4 |
| 4 | 1 |
| 5 | 1 |
Array size:
7
Majority:
count > 3
Element:
3
Array Visualization
Input:
[3,2,3,3,1,3]
Visual:
3 2 3 3 1 3
↑ ↑ ↑ ↑
3 appears 4 times
Length:
6
Threshold:
6/2 = 3
Since:
4 > 3
Answer:
3
Dry Run
Input:
[2,2,1,1,1,2,2]
Initial:
count = 0
Read:
2
Count:
1
Candidate:
2
Read:
2
Count:
2
Read:
1
Count:
1
Read:
1
Count:
0
Candidate changes.
Read:
1
Count:
1
Read:
2
Count:
0
Read:
2
Count:
1
Final candidate:
2
Approach 1 — Brute Force Counting Approach
The simplest solution:
For every element:
- Count how many times it appears.
- Check if count is greater than
n/2.
Algorithm
- Pick an element.
- Traverse complete array.
- Count occurrences.
- Return if:
count > n/2
Java Program
public class MajorityElementBruteForce {
public static int findMajority(
int[] nums) {
int n = nums.length;
for (int i = 0;
i < n;
i++) {
int count = 0;
for (int j = 0;
j < n;
j++) {
if (nums[i] == nums[j]) {
count++;
}
}
if (count > n / 2) {
return nums[i];
}
}
return -1;
}
public static void main(String[] args) {
int[] nums =
{2,2,1,1,1,2,2};
System.out.println(
findMajority(nums));
}
}
Output
2
Step-by-Step Explanation
Input:
[2,2,1,1,1,2,2]
Check:
2
Count:
4
Array length:
7
Threshold:
3
Condition:
4 > 3
Return:
2
Complexity Analysis
Outer loop:
O(n)
Inner counting loop:
O(n)
Total:
O(n²)
Space:
O(1)
Advantages
- Very simple.
- Easy to understand.
- No extra memory.
Drawbacks
- Slow for large arrays.
- Repeats unnecessary counting.
- Not suitable for production.
Approach 2 — Sorting Approach
Observation:
After sorting, the majority element always appears in the middle.
Why?
Because it appears more than half of the array.
Example
Input:
[3,2,3,2,3]
Sort:
[2,2,3,3,3]
Middle element:
index = n/2
3
Answer:
3
Algorithm
- Sort the array.
- Return:
nums[n/2]
Java Program
import java.util.Arrays;
public class MajorityElementSorting {
public static int findMajority(
int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
public static void main(String[] args) {
int[] nums =
{2,2,1,1,1,2,2};
System.out.println(
findMajority(nums));
}
}
Output
2
Step-by-Step Explanation
Input:
[2,2,1,1,1,2,2]
Sort:
[1,1,1,2,2,2,2]
Length:
7
Middle index:
7/2 = 3
Value:
2
Complexity Analysis
Sorting:
O(n log n)
Access:
O(1)
Overall:
O(n log n)
Space:
O(1)
(depending on sorting implementation)
Advantages
- Simple implementation.
- Better than brute force.
- Easy interview explanation.
Drawbacks
- Sorting is unnecessary.
- Modifies original array.
- Not optimal.
Approach 3 — HashMap Frequency Approach
HashMap stores:
Element → Frequency
Example:
Input:
[2,2,1,1,1,2,2]
Frequency:
2 → 4
1 → 3
Majority:
2
Algorithm
- Create HashMap.
- Traverse array.
- Increase frequency.
- Check if frequency exceeds:
n/2
- Return element.
Java Program
import java.util.HashMap;
import java.util.Map;
public class MajorityElementHashMap {
public static int findMajority(
int[] nums) {
Map<Integer,Integer> map =
new HashMap<>();
int limit =
nums.length / 2;
for (int num : nums) {
map.put(
num,
map.getOrDefault(
num,0)+1);
if (map.get(num) > limit) {
return num;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums =
{2,2,1,1,1,2,2};
System.out.println(
findMajority(nums));
}
}
Output
2
Complexity Analysis
Time:
O(n)
Space:
O(n)
Advantages
- Linear time.
- Easy to understand.
- Useful for frequency problems.
Drawbacks
- Requires extra memory.
- HashMap overhead.
Approach 4 — Boyer-Moore Voting Algorithm (Optimal Solution)
The Boyer-Moore Voting Algorithm is the most efficient solution for finding the majority element.
It provides:
Time Complexity: O(n)
Space Complexity: O(1)
This is the preferred interview solution.
Core Idea
The majority element appears more than:
n / 2
times.
This means:
The majority element count is greater than all other elements combined.
Therefore, if we cancel one different element against one occurrence of the majority element, the majority element will still remain.
Voting Concept
Think of each element as a vote.
Example:
[2,2,1,1,1,2,2]
Votes:
2 → +1
1 → -1
After cancellation:
2 remains
Algorithm
Maintain two variables:
Candidate
Stores possible majority element.
candidate
Count
Tracks voting balance.
count
Rules:
Case 1
If count becomes:
0
choose current element as candidate.
Case 2
If current element equals candidate:
Increase:
count++
Case 3
If current element is different:
Decrease:
count--
Example Dry Run
Input:
[2,2,1,1,1,2,2]
Initial:
candidate = none
count = 0
Read:
2
count is zero.
Choose:
candidate = 2
Count:
1
Read:
2
Same candidate.
Count:
2
Read:
1
Different.
Count:
1
Read:
1
Different.
Count:
0
Read:
1
Count is zero.
New candidate:
1
Count:
1
Read:
2
Different.
Count:
0
Read:
2
New candidate:
2
Count:
1
Final candidate:
2
Java Program
public class MajorityElementBoyerMoore {
public static int findMajority(
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;
}
public static void main(String[] args) {
int[] nums =
{2,2,1,1,1,2,2};
System.out.println(
findMajority(nums));
}
}
Output
2
Step-by-Step Explanation
Input:
[2,2,1,1,1,2,2]
Candidate:
2
Voting:
+1
+1
-1
-1
+1
-1
+1
Final balance:
positive
Winner:
2
Complexity Analysis
Time:
O(n)
Each element is processed once.
Space:
O(1)
Only two variables are used.
Advantages
- Optimal solution.
- No extra memory.
- Single traversal.
- Works with very large arrays.
Drawbacks
- Requires understanding of voting logic.
- Does not automatically verify majority existence.
Mathematical Proof of Boyer-Moore Algorithm
Assume:
Majority element:
M
Frequency:
> n/2
Other elements combined:
< n/2
During cancellation:
Every non-majority element can cancel at most one majority element.
Because:
Majority count > Other count
After all cancellations:
Majority element remains.
Therefore:
candidate = majority element
Majority Element Verification
The original problem assumes a majority element exists.
But some problems do not.
Example:
[1,2,3,4]
No element appears more than:
4/2 = 2
times.
Boyer-Moore returns a candidate, but we need validation.
Verification Algorithm
After finding candidate:
- Count occurrences.
- Check:
count > n/2
Java Program
public class MajorityElementVerification {
public static Integer findMajority(
int[] nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count +=
(num == candidate)
? 1
: -1;
}
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
if (count > nums.length / 2) {
return candidate;
}
return null;
}
}
Complexity Analysis
Time:
O(n)
Space:
O(1)
Majority Element II — N/3 Variant
A common interview follow-up:
Find all elements appearing more than n/3 times.
Example
Input:
[3,2,3]
n:
3
Threshold:
n/3 = 1
Elements appearing more than one time:
3
Output:
[3]
Important Difference
For:
n/2
There can be:
Only one majority element
For:
n/3
There can be:
At most two elements
Boyer-Moore Extension
Maintain:
candidate1
count1
candidate2
count2
Java Program
import java.util.*;
public class MajorityElementNByThree {
public static List<Integer> findMajority(
int[] nums) {
Integer candidate1 = null;
Integer candidate2 = null;
int count1 = 0;
int count2 = 0;
for (int num : nums) {
if (candidate1 != null &&
num == candidate1) {
count1++;
} else if (candidate2 != null &&
num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1++;
} else if (count2 == 0) {
candidate2 = num;
count2++;
} else {
count1--;
count2--;
}
}
List<Integer> result =
new ArrayList<>();
for (Integer candidate :
Arrays.asList(candidate1,
candidate2)) {
if (candidate != null) {
int count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
if (count > nums.length / 3) {
result.add(candidate);
}
}
}
return result;
}
}
Java Streams Approach
Streams can solve majority element using grouping.
Example:
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
public class MajorityElementStreams {
public static int findMajority(
int[] nums) {
return Arrays.stream(nums)
.boxed()
.collect(
Collectors.groupingBy(
Function.identity(),
Collectors.counting()))
.entrySet()
.stream()
.filter(entry ->
entry.getValue()
> nums.length / 2)
.map(Map.Entry::getKey)
.findFirst()
.orElse(-1);
}
}
Complexity Analysis
Time:
O(n)
Space:
O(n)
Comparison of All Approaches
| Approach | Time | Space | Best Use Case |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Learning |
| Sorting | O(n log n) | O(1) | Simple solution |
| HashMap | O(n) | O(n) | Frequency problems |
| Boyer-Moore | O(n) | O(1) | Best interview solution |
| Streams | O(n) | O(n) | Functional style |
Primitive vs Object Arrays
Primitive Array
Example:
int[]
Advantages:
- Faster.
- Less memory.
- Better performance.
Object Array
Example:
Integer[]
Advantages:
- Works with Collections.
- Supports Streams.
Common Interview Mistakes
Mistake 1
Using HashMap when O(1) space is expected.
Mistake 2
Forgetting majority verification.
Boyer-Moore gives:
Candidate
not always guaranteed answer.
Mistake 3
Confusing:
n/2
with:
n/3
Mistake 4
Sorting unnecessarily.
Edge Cases
| Input | Output |
|---|---|
[1] |
1 |
[2,2,2] |
2 |
[-1,-1,2] |
-1 |
[1,2,3] |
No majority |
| Large array | Use Boyer-Moore |
Interview Follow-up Questions
Q1. Find majority element in O(1) space.
Q2. Explain Boyer-Moore voting algorithm.
Q3. Why does cancellation work?
Q4. Find elements appearing more than n/3 times.
Q5. Verify majority element.
Q6. Find most frequent element.
Q7. Solve for streaming data.
Related Problems
- Find Duplicate Number
- Missing Number
- Top K Frequent Elements
- Frequency Counting
- Single Number
- Voting Algorithms
Key Takeaways
Majority Element is a classic example of optimization.
Solutions:
Brute Force
↓
Sorting
↓
HashMap
↓
Boyer-Moore Voting
The optimal interview solution:
Boyer-Moore Voting Algorithm
Complexity:
Time: O(n)
Space: O(1)
Core idea:
A majority element can survive cancellation with all other elements because it appears more than half of the array.
Frequently Asked Interview Questions
Q1. What is the optimal approach?
Boyer-Moore Voting Algorithm.
Q2. Why does it use constant space?
Because it only maintains:
candidate
count
Q3. Can there be two majority elements?
For:
n/2
No.
For:
n/3
Maximum two.
Q4. Where is this algorithm useful?
Applications:
- Voting systems
- Data streams
- Consensus algorithms
- Frequency analysis
Interview Tip
When asked:
"Find the majority element."
Explain the evolution:
- Brute Force → O(n²)
- Sorting → O(n log n)
- HashMap → O(n) with extra space
- Boyer-Moore → O(n), O(1)
For senior-level interviews, always explain:
Why cancellation works
not just the code.
This demonstrates strong understanding of greedy algorithms, memory optimization, and problem-solving techniques.