.png)
Find the Majority Element (Moore’s Voting Algorithm)
Problem Statement
You are given an array of integers of size n.
A majority element is an element that appears more than ⌊n / 2⌋ times in the array.
You need to find and return the majority element.
Assumption: The majority element always exists.
Example 1
Input
arr = [3, 2, 3]
Output
3
Example 2
Input
arr = [2, 2, 1, 1, 1, 2, 2]
Output
2
Why This Problem Is Important
- Extremely common interview question
- Tests array traversal and frequency logic
- Introduces cancellation principle
- Foundation for optimized frequency problems
- Leads to Moore’s Voting Algorithm
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Hash Map / Frequency Count | O(n) | O(n) |
| Approach 3 | Moore’s Voting Algorithm | O(n) | O(1) |
Approach 1: Brute Force
Idea
For each element, count how many times it appears in the array.
If the count exceeds n/2, that element is the majority element.
Algorithm
- Loop through each element i
- Initialize count = 0
- Loop again to count occurrences of arr[i]
- If count > n/2, return arr[i]
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {2,2,1,1,1,2,2};
int n = 7;
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(arr[i] == arr[j])
count++;
}
if(count > n/2) {
printf("%d", arr[i]);
break;
}
}
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {2,2,1,1,1,2,2};
int n = 7;
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(arr[i] == arr[j])
count++;
}
if(count > n/2) {
cout << arr[i];
break;
}
}
return 0;
}
Java
public class MajorityElement {
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
int n = arr.length;
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(arr[i] == arr[j])
count++;
}
if(count > n/2) {
System.out.print(arr[i]);
break;
}
}
}
}
Python
arr = [2,2,1,1,1,2,2]
n = len(arr)
for i in range(n):
count = 0
for j in range(n):
if arr[i] == arr[j]:
count += 1
if count > n//2:
print(arr[i])
break
JavaScript
let arr = [2,2,1,1,1,2,2];
let n = arr.length;
for (let i = 0; i < n; i++) {
let count = 0;
for (let j = 0; j < n; j++) {
if (arr[i] === arr[j])
count++;
}
if (count > Math.floor(n / 2)) {
console.log(arr[i]);
break;
}
}
Approach 2: Hash Map / Frequency Count
Idea
Store frequency of each element using a map.
Return the element whose frequency exceeds n/2.
Algorithm
- Create an empty map
- Traverse the array
- Increment frequency of each element
- If frequency > n/2, return the element
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {2,2,1,1,1,2,2};
int n = 7;
unordered_map freq;
for(int i = 0; i < n; i++) {
freq[arr[i]]++;
if(freq[arr[i]] > n/2) {
cout << arr[i];
break;
}
}
return 0;
}
Java
import java.util.HashMap;
public class MajorityElement {
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
HashMap map = new HashMap<>();
for(int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
if(map.get(num) > arr.length / 2) {
System.out.print(num);
break;
}
}
}
}
Python
arr = [2,2,1,1,1,2,2]
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
if freq[num] > len(arr)//2:
print(num)
break
JavaScript
let arr = [2,2,1,1,1,2,2];
let freq = {};
for (let num of arr) {
freq[num] = (freq[num] || 0) + 1;
if (freq[num] > Math.floor(arr.length / 2)) {
console.log(num);
break;
}
}
Approach 3: Moore’s Voting Algorithm (Optimal)
Idea
If an element appears more than n/2 times, it will never be fully cancelled out by other elements.
Maintain:
- candidate
- count
Algorithm
- Initialize count = 0, candidate = None
- Traverse the array
- If count == 0, set candidate = current element
- If current element == candidate → count++
- Else → count--
- candidate will be the majority element
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {2,2,1,1,1,2,2};
int n = 7;
int count = 0, candidate = 0;
for(int i = 0; i < n; i++) {
if(count == 0)
candidate = arr[i];
if(arr[i] == candidate)
count++;
else
count--;
}
printf("%d", candidate);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {2,2,1,1,1,2,2};
int count = 0, candidate = 0;
for(int num : arr) {
if(count == 0)
candidate = num;
if(num == candidate)
count++;
else
count--;
}
cout << candidate;
return 0;
}
Java
public class MajorityElement {
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
int count = 0, candidate = 0;
for(int num : arr) {
if(count == 0)
candidate = num;
if(num == candidate)
count++;
else
count--;
}
System.out.print(candidate);
}
}
Python
arr = [2,2,1,1,1,2,2]
count = 0
candidate = None
for num in arr:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
print(candidate)
JavaScript
let arr = [2,2,1,1,1,2,2];
let count = 0, candidate = null;
for (let num of arr) {
if (count === 0) candidate = num;
count += (num === candidate) ? 1 : -1;
}
console.log(candidate);
Dry Run (Moore’s Voting Algorithm)
Input
[2, 2, 1, 1, 1, 2, 2]
| Element | Candidate | Count |
|---|---|---|
| 2 | 2 | 1 |
| 2 | 2 | 2 |
| 1 | 2 | 1 |
| 1 | 2 | 0 |
| 1 | 1 | 1 |
| 2 | 1 | 0 |
| 2 | 2 | 1 |
Final Answer
2
Summary
- Brute force is simple but inefficient
- Hash map improves time but uses extra space
- Moore’s Voting Algorithm is optimal and interview-preferred
- Solves the problem in one pass with constant space
Next Problem in the Series
.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)
