Find All Elements that Appear More than N/K Times

Title: Find All Elements that Appear More than N/K Times

Given an array of size N and an integer K, we want every element that appears strictly more than N/K times. In this guide, you’ll learn a clean generalization of the Boyer-Moore majority vote that solves the problem in linear time with only K - 1 counters, no sorting, and no hash map blowup.

The problem is a classic interview favorite because it probes whether you can extend a well-known algorithm (N/2 majority) to a parameterized version. Let’s explore the idea, write a working Java program, trace it on a small input, and finish with the follow-up questions you should expect from an interviewer.

Understanding the Problem

The threshold is N/K, computed using integer division. For an array of size N = 8 and K = 4, the threshold is 2, so we must return every value that appears at least three times. There can be at most K - 1 such values; if K or more values each appeared more than N/K times, their total count would already exceed N.

The naive solution counts frequencies with a hash map in O(N) time and O(N) space. The improved approach we focus on in this post keeps only K - 1 counters, which brings the extra memory down to O(K) regardless of how many distinct values the array holds.

Approach to Find Elements More than N/K Times

The algorithm has two linear passes over the array. The first pass narrows the search to at most K - 1 candidates. The second pass verifies which candidates actually meet the threshold.

1. Compute the threshold threshold = N / K using integer division.
2. Keep a map candidates that holds at most K - 1 entries, each mapping a value to a running counter.
3. For each element value in the array, if value is already a candidate, increment its counter.
4. Otherwise, if candidates has fewer than K - 1 entries, add value with counter 1.
5. Otherwise, decrement the counter of every current candidate; drop any candidate whose counter falls to 0.
6. After the first pass, do a second pass that counts the actual occurrences of each surviving candidate in the original array.
7. Return every surviving candidate whose actual count is strictly greater than threshold.

Java Program to Find Elements More than N/K Times

Here is the full, compilable program. The findElements method implements the two-pass algorithm, and main drives it with a sample input.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ElementsMoreThanNByK {

    public static List<Integer> findElements(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k < 2) {
            return new ArrayList<>();
        }
        int n = arr.length;
        int threshold = n / k;

        Map<Integer, Integer> candidates = new HashMap<>();
        for (int value : arr) {
            if (candidates.containsKey(value)) {
                candidates.put(value, candidates.get(value) + 1);
            } else if (candidates.size() < k - 1) {
                candidates.put(value, 1);
            } else {
                List<Integer> toRemove = new ArrayList<>();
                for (Map.Entry<Integer, Integer> entry : candidates.entrySet()) {
                    if (entry.getValue() == 1) {
                        toRemove.add(entry.getKey());
                    } else {
                        entry.setValue(entry.getValue() - 1);
                    }
                }
                for (int key : toRemove) {
                    candidates.remove(key);
                }
            }
        }

        Map<Integer, Integer> finalCounts = new HashMap<>();
        for (int key : candidates.keySet()) {
            finalCounts.put(key, 0);
        }
        for (int value : arr) {
            if (finalCounts.containsKey(value)) {
                finalCounts.put(value, finalCounts.get(value) + 1);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : finalCounts.entrySet()) {
            if (entry.getValue() > threshold) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 2, 1, 2, 3, 3};
        int k = 4;
        List<Integer> result = findElements(arr, k);
        System.out.println("Elements appearing more than N/K times: " + result);
    }
}

Explanation of the Program

• findElements first guards against a null array, an empty array, and k < 2; the problem is only meaningful when k is at least 2.
• threshold = n / k uses integer division; the returned values must appear strictly more than this count.
• The candidates map stores at most k - 1 live counters at any moment. A new value is either added, matched, or forces a global decrement.
• The toRemove list avoids a ConcurrentModificationException while iterating the entries. Keys whose counter would drop to 0 are deleted after the loop.
• The second pass fills finalCounts with the real occurrences of the surviving candidates so the verification step is exact.
• Finally, the method collects every value whose actual count exceeds threshold and returns the list.

Step-by-Step Trace

Let’s trace the algorithm on arr = {1, 1, 2, 3, 1} with k = 3. Here n = 5, so threshold = 5 / 3 = 1 and we can keep at most k - 1 = 2 candidates. The expected answer is [1] because only 1 appears more than one time.

After the first pass, the only survivor is 1. The verification pass counts its real occurrences and finds 3, which is greater than threshold = 1, so the final answer is [1]. At the end of each iteration, every key in candidates is a possible winner and no non-winner is guaranteed to be present.

Examples

Here are a few runs of findElements that show how the output changes with K and the input distribution.

Example 1: No Element Qualifies

When every value appears the same small number of times, the threshold rules out all of them and the result is an empty list.

int[] arr = {1, 2, 3, 4};
int k = 2;
List<Integer> result = findElements(arr, k);

System.out.println(result);
// Output: []

Example 2: Two Winners for K = 4

With n = 8 and k = 4, the threshold is 2, and both 2 and 3 appear three times.

int[] arr = {3, 1, 2, 2, 1, 2, 3, 3};
int k = 4;
List<Integer> result = findElements(arr, k);

System.out.println(result);
// Output: [2, 3]  (order may vary)

Example 3: Clear Majority for K = 3

The threshold here is n / k = 6 / 3 = 2. The value 4 appears four times (greater than 2), while 2 appears exactly 2 times and does not qualify.

int[] arr = {4, 4, 4, 4, 2, 2};
int k = 3;
List<Integer> result = findElements(arr, k);

System.out.println(result);
// Output: [4]

Common Mistakes to Avoid

These are the slips interviewers watch for on this problem. Each one changes the output on a specific input, so they are easy to miss without a careful trace.

• Using >= instead of > – returns elements that appear exactly N/K times, which the problem rules out. For arr = {1, 1, 2, 2} and k = 2 the buggy code returns [1, 2]; the correct answer is [].
• Skipping the verification pass – the candidates from the first pass are only possibilities, not guarantees. Omitting the second pass can return non-winners when fewer than K - 1 real winners exist.
• Keeping K counters instead of K – 1 – the invariant breaks because you cannot force a decrement anymore. Always cap candidates at K - 1 entries.
• Decrementing without removing zeros – leaving entries with counter 0 wastes a slot and may let a non-winner survive. Remove every key that falls to 0 before processing the next element.
• Mutating the map while iterating – calling candidates.remove(key) inside the entrySet() loop throws ConcurrentModificationException. Collect keys in a side list and delete after the loop.

Edge Cases to Test

A good interview answer walks through boundary inputs before writing a line of production code. For this problem the useful checks are:

• Empty array
• Single-element array
• K = 1 or K larger than N
• All elements identical
• All elements distinct
• Exactly K - 1 winners tied at the threshold boundary
• Negative values and Integer.MIN_VALUE present
• null array reference

Additional Considerations

The two passes together run in O(N * K) time in the worst case because the decrement step touches up to K - 1 counters for every element. Since K is typically a small constant (2, 3, 4), this is effectively linear time: O(N).

The extra space is O(K) for the candidates and finalCounts maps combined. That is a big win over the naive hash-map approach, which uses O(D) extra memory where D is the number of distinct values in the array.

Watch for integer overflow in the threshold only if N is close to Integer.MAX_VALUE. The counts themselves are bounded by N, so int is safe for arrays that fit in memory.

Interview Follow-up Questions

Once the base solution is on the whiteboard, interviewers typically push on complexity, constraints, and extensions. Expect questions like these.

• What if K = 2? – the algorithm collapses to the classic Boyer-Moore majority vote with a single candidate and a single counter.
• Can you avoid the verification pass? – no, because the first pass only narrows the search; without recounting you may return a non-winner when the input has fewer than K - 1 true winners.
• What if the input is a stream of unknown length? – keep the K - 1 candidates and counters as streaming state; emit the final verification only once the stream ends or you can afford a second pass over a buffered window.
• What if the array is immutable and you cannot use extra arrays? – the K - 1 counters are the entire extra state, which already satisfies the O(K) memory bound; the verification pass is read-only.
• What if the array has billions of elements across many machines? – compute the local K - 1 candidate maps per shard in parallel, merge them pairwise using the same decrement rule, then run the verification pass once over the full data.

Conclusion

The N/K majority problem is a tidy generalization of the classic majority element question. By keeping only K - 1 counters and following them with one verification pass, the algorithm runs in effectively linear time with constant extra memory. The pattern is worth internalizing because it shows up in streaming analytics, heavy-hitter detection, and network-traffic sketching.

Try adapting the code to return the actual frequencies alongside the winning values, or to work on a List<String> instead of an int[]. The structure stays the same; only the counter map’s key type changes.

You can learn more about Array problems: Arrays.