.png)
Find the Majority Element in an Array
Problem Statement
Given an array of n elements, find the majority element.
- A majority element is an element that appears more than n/2 times in the array.
- If no element occurs more than n/2 times, return no majority element.
- This problem is commonly asked in interviews and tests understanding of arrays, counting, and hashing techniques.
Example 1
Input:
arr = [3, 3, 4, 2, 3, 3, 5]
Output:
3
Explanation:
- Array size n = 7
- n/2 = 3.5 → an element must appear more than 3 times
- Element 3 appears 4 times → majority element.
Example 2
Input:
arr = [1, 2, 3, 4]
Output:
No majority element
Explanation:
- Array size n = 4
- n/2 = 2 → element must appear more than 2 times
- No element appears more than twice → no majority element.
Why This Problem Is Important
- Tests array traversal, counting, and hashing skills.
- Foundation for Boyer-Moore Voting Algorithm (optimal solution).
- Helps understand frequency-based problems and threshold detection.
Approaches to Solve the Problem
- Brute Force (Nested Loops) ✅ S0imple but slow
- Hashing / Frequency Map (Efficient) ✅ Most commonly used in interviews
- Boyer-Moore Voting Algorithm ✅ Optimal, O(n) time, O(1) space
In this post, we focus on Brute Force and Hashing approaches.
Approach 1: Brute Force
Idea
- For each element in the array, count its occurrences by traversing the array.
- If any element occurs more than n/2 times, return it.
- Otherwise, return no majority element.
Time & Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
C++ Implementation (Brute Force)
#include
#include
using namespace std;
int main() {
vector arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.size();
bool found = false;
for(int i=0; i n/2) {
cout << "Majority element: " << arr[i];
found = true;
break;
}
}
if(!found) cout << "No majority element";
}
Java Implementation (Brute Force)
public class MajorityElementBrute {
public static void main(String[] args) {
int[] arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.length;
boolean found = false;
for(int i=0; i n/2) {
System.out.println("Majority element: " + arr[i]);
found = true;
break;
}
}
if(!found) System.out.println("No majority element");
}
}
Approach 2: Using Hashing / Frequency Map
Idea
- Traverse the array and maintain a frequency map.
- For each element, increment its count.
- If any element occurs more than n/2 times, return it.
Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
Python Implementation (Hashing)
arr = [3, 3, 4, 2, 3, 3, 5]
n = len(arr)
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
majority = None
for num, count in freq.items():
if count > n//2:
majority = num
break
if majority:
print("Majority element:", majority)
else:
print("No majority element")
C++ Implementation (Hashing)
#include
#include
#include
using namespace std;
int main() {
vector arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.size();
unordered_map freq;
for(int num : arr) freq[num]++;
bool found = false;
for(auto it : freq) {
if(it.second > n/2) {
cout << "Majority element: " << it.first;
found = true;
break;
}
}
if(!found) cout << "No majority element";
}
JavaScript Implementation (Hashing)
let arr = [3, 3, 4, 2, 3, 3, 5];
let freq = {};
let n = arr.length;
arr.forEach(num => freq[num] = (freq[num] || 0) + 1);
let majority = null;
for(let key in freq){
if(freq[key] > n/2){
majority = Number(key);
break;
}
}
if(majority) console.log("Majority element:", majority);
else console.log("No majority element");
Approach 3: Boyer-Moore Voting Algorithm
Idea
- Maintain a candidate element and a count.
- Traverse the array:
- If count = 0, set the current element as the candidate.
- If the current element == candidate, increment count.
- Else, decrement count.
- After traversal, the candidate may be the majority element.
- Verify if the candidate occurs more than n/2 times.
Time & Space Complexity
- Time Complexity: O(n) → one pass to find candidate + one pass to verify
- Space Complexity: O(1)
Python Implementation
arr = [3, 3, 4, 2, 3, 3, 5]
n = len(arr)
# Step 1: Find candidate
candidate = None
count = 0
for num in arr:
if count == 0:
candidate = num
count = 1
elif num == candidate:
count += 1
else:
count -= 1
# Step 2: Verify candidate
if arr.count(candidate) > n // 2:
print("Majority element:", candidate)
else:
print("No majority element")
C++ Implementation
#include
#include
using namespace std;
int main() {
vector arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.size();
// Step 1: Find candidate
int candidate = 0, count = 0;
for(int num : arr){
if(count == 0){
candidate = num;
count = 1;
} else if(num == candidate) {
count++;
} else {
count--;
}
}
// Step 2: Verify candidate
count = 0;
for(int num : arr){
if(num == candidate) count++;
}
if(count > n/2)
cout << "Majority element: " << candidate;
else
cout << "No majority element";
}
Java Implementation
public class MajorityElementBoyerMoore {
public static void main(String[] args) {
int[] arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.length;
// Step 1: Find candidate
int candidate = 0, count = 0;
for(int num : arr){
if(count == 0){
candidate = num;
count = 1;
} else if(num == candidate){
count++;
} else {
count--;
}
}
// Step 2: Verify candidate
count = 0;
for(int num : arr){
if(num == candidate) count++;
}
if(count > n/2)
System.out.println("Majority element: " + candidate);
else
System.out.println("No majority element");
}
}
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {3, 3, 4, 2, 3, 3, 5};
int n = arr.Length;
// Step 1: Find candidate
int candidate = 0, count = 0;
foreach(int num in arr){
if(count == 0){
candidate = num;
count = 1;
} else if(num == candidate){
count++;
} else {
count--;
}
}
// Step 2: Verify candidate
count = 0;
foreach(int num in arr){
if(num == candidate) count++;
}
if(count > n/2)
Console.WriteLine("Majority element: " + candidate);
else
Console.WriteLine("No majority element");
}
}
JavaScript Implementation
let arr = [3, 3, 4, 2, 3, 3, 5];
let n = arr.length;
// Step 1: Find candidate
let candidate = null;
let count = 0;
for(let num of arr){
if(count === 0){
candidate = num;
count = 1;
} else if(num === candidate){
count++;
} else {
count--;
}
}
// Step 2: Verify candidate
count = arr.filter(x => x === candidate).length;
if(count > Math.floor(n/2))
console.log("Majority element:", candidate);
else
console.log("No majority element");
Summary of Approaches for Majority Element
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Simple, inefficient |
| Hashing / Frequency Map | O(n) | O(n) | Common in interviews |
| Boyer-Moore Voting | O(n) | O(1) | Optimal solution, widely asked in interviews |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
