Given an array of size n and a number k, find all elements that appear more than n/k times

The problem, simply

You get an array of n numbers and a number k. Find every number that appears more than n / k times.

A useful fact: at most k - 1 numbers can do this. If k numbers each appeared more than n / k times, together they would need more than n boxes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count every number with a hash map, then keep the ones with a big enough count. (An even simpler first try, counting each number by walking the whole array again, takes O(n^2).)

1. Walk the array and count each number.
2. Return every number whose count is more than n / k.

class Solution {
    public List<Integer> moreThanNByK(int[] arr, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) count.merge(x, 1, Integer::sum);
        List<Integer> out = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            if (e.getValue() > arr.length / k) out.add(e.getKey());
        }
        return out;
    }
}

How long it takes: O(n). Extra room: one entry per different number, up to O(n). Fine for most uses, but if the array is a huge stream with millions of different numbers, the map gets huge.

Way 2: the clever way

Keep a bench of at most k - 1 candidates with tallies.

1. For each x: if x is on the bench, add 1 to its tally.
2. Else if the bench has a free seat, put x there with tally 1.
3. Else lower every tally by 1 and remove the ones that reach 0. (x is also thrown away: it cancels with them.)
4. After the walk, the bench holds every possible answer, plus maybe some false ones. Count the bench numbers for real in a second walk and keep those with more than n / k.

class Solution {
    public List<Integer> moreThanNByK(int[] arr, int k) {
        List<Integer> out = new ArrayList<>();
        if (k < 2) return out;                         // nothing appears more than n times
        Map<Integer, Integer> bench = new HashMap<>();
        for (int x : arr) {
            if (bench.containsKey(x)) {
                bench.put(x, bench.get(x) + 1);        // team already seated
            } else if (bench.size() < k - 1) {
                bench.put(x, 1);                       // a free seat
            } else {                                   // full: k different numbers cancel
                Iterator<Map.Entry<Integer, Integer>> it = bench.entrySet().iterator();
                while (it.hasNext()) {
                    Map.Entry<Integer, Integer> e = it.next();
                    if (e.getValue() == 1) it.remove();
                    else e.setValue(e.getValue() - 1);
                }
            }
        }
        for (int key : bench.keySet()) bench.put(key, 0);   // second walk: real counts
        for (int x : arr) if (bench.containsKey(x)) bench.put(x, bench.get(x) + 1);
        for (Map.Entry<Integer, Integer> e : bench.entrySet()) {
            if (e.getValue() > arr.length / k) out.add(e.getKey());
        }
        return out;
    }
}

How long it takes: a cancel costs O(k), which looks like O(n * k) in total. But each cancel removes k - 1 tally points, and tallies only ever gain n points, so there are at most n / (k - 1) cancels. The total is O(n). Extra room: the bench, O(k).

Watch out for

• "More than n / k" is strict. With n = 8, k = 4, a number appearing exactly 2 times does not count. With integer division, count > n / k is still exactly right.
• When the bench is full and x is new, x is not seated. It cancels with the others.
• Removing from a HashMap while looping over it needs an iterator's remove, or you get a ConcurrentModificationException.

What interviewers ask next

• k = 2, the majority? Keep one candidate and one tally: same number adds 1, different number subtracts 1, tally 0 means take the new number. That is Boyer-Moore voting, O(n) time and O(1) room.
• k = 3 (LeetCode Majority Element II)? Two candidates, two tallies, then verify. Same as this with a bench of 2.
• Why at most k - 1 answers? If k numbers each had more than n / k copies, there would be more than n boxes.
• A huge stream where you cannot do a second walk? The bench still gives every heavy number, plus false ones, and each tally is at most n / k below the true count. This is the Misra-Gries summary used for heavy hitters in network traffic.

Remember this

Grown-up words: the bench is a set of candidates with counters, cancelling k different items is the Misra-Gries heavy hitters algorithm, and k = 2 is the Boyer-Moore majority vote.