Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. At most two different values can each appear more than n/3 times.
  2. 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);
        }
    }
}

Solve Majority Element II online · All practice problems