Practice › Arrays
Majority Element
Medium · Arrays · Asked at Amazon, Microsoft, Google, Adobe
Find the element that appears more than n/2 times. Such an element always exists.
Input
First line: n. Second line: n space-separated integers.
Output
The majority element.
Constraints
- 1 ≤ n ≤ 10^5
Moore's Voting Algorithm does it in O(n) time and O(1) space.
Example 1
Input
3 3 2 3
Output
3
Example 2
Input
7 2 2 1 1 1 2 2
Output
2
Hints
- A hash map of counts works in O(n) space. Can you do it in O(1)?
- Moore's voting: keep a candidate and a counter; equal values add a vote, different values remove one.
Approach
Moore's voting algorithm pairs off different values against each other. Keep candidate and count: when count is 0, adopt the current value; same value → count++, different → count--. The majority element appears more than n/2 times, so it can't be fully cancelled and is the final candidate.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long candidate = 0, x;
int count = 0;
for (int i = 0; i < n; i++) {
cin >> x;
if (count == 0) candidate = x;
count += (x == candidate) ? 1 : -1;
}
cout << candidate << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
candidate, count = 0, 0
for x in data[1 : data[0] + 1]:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
print(candidate)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), count = 0;
long candidate = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
if (count == 0) candidate = x;
count += (x == candidate) ? 1 : -1;
}
System.out.println(candidate);
}
}