Practice › Arrays
Majority Element II
Medium · Arrays · Asked at Amazon, Google, Microsoft, Zoho
Print every value that appears more than ⌊n/3⌋ times, in increasing order. If there is none, print -1.
Input
First line: n. Second line: n space-separated integers.
Output
The values, space-separated, or -1.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
At most two values can qualify. Extended Boyer–Moore voting keeps two candidates, then a second pass verifies them.
Example 1
Input
3 3 2 3
Output
3
Example 2
Input
4 1 2 3 4
Output
-1
Hints
- At most two different values can each appear more than n/3 times.
- Keep two candidates with counters (extended Boyer–Moore voting), then count them again to verify.
Approach
Voting: for each x, if it equals a candidate, increase that counter; else if a counter is 0, make x that candidate; otherwise decrease both counters (this "cancels" three different values at once). Any value occurring more than n/3 times survives as a candidate, but a candidate is not guaranteed to qualify — so do a second pass counting both candidates exactly. Print the qualifying ones in increasing order, or -1.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long c1 = 0, c2 = 1;
int k1 = 0, k2 = 0;
for (long long x : a) {
if (x == c1) k1++;
else if (x == c2) k2++;
else if (k1 == 0) c1 = x, k1 = 1;
else if (k2 == 0) c2 = x, k2 = 1;
else k1--, k2--;
}
k1 = k2 = 0;
for (long long x : a) {
if (x == c1) k1++;
else if (x == c2) k2++;
}
vector<long long> res;
if (k1 > n / 3) res.push_back(c1);
if (k2 > n / 3) res.push_back(c2);
sort(res.begin(), res.end());
if (res.empty()) cout << -1 << "\n";
for (size_t i = 0; i < res.size(); i++) cout << res[i] << (i + 1 < res.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
c1, c2, k1, k2 = 0, 1, 0, 0
for x in a:
if x == c1:
k1 += 1
elif x == c2:
k2 += 1
elif k1 == 0:
c1, k1 = x, 1
elif k2 == 0:
c2, k2 = x, 1
else:
k1 -= 1
k2 -= 1
res = sorted(c for c in (c1, c2) if a.count(c) > n // 3)
print(*res if res else [-1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long c1 = 0, c2 = 1;
int k1 = 0, k2 = 0;
for (long x : a) {
if (x == c1) k1++;
else if (x == c2) k2++;
else if (k1 == 0) { c1 = x; k1 = 1; }
else if (k2 == 0) { c2 = x; k2 = 1; }
else { k1--; k2--; }
}
k1 = 0;
k2 = 0;
for (long x : a) {
if (x == c1) k1++;
else if (x == c2) k2++;
}
List<Long> res = new ArrayList<>();
if (k1 > n / 3) res.add(c1);
if (k2 > n / 3) res.add(c2);
Collections.sort(res);
if (res.isEmpty()) System.out.println(-1);
else {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) sb.append(res.get(i)).append(i + 1 < res.size() ? " " : "");
System.out.println(sb);
}
}
}