At Least K Occurrences

Problem Overview

The answer is the first value whose running count reaches k while the array is scanned from left to right.

Intuition

The answer is the first value whose running count reaches k while the array is scanned from left to right. That moment is the earliest k-th occurrence of any value, so later values that also reach k do not replace it. Because every array entry lies between 0 and one million, a frequency array of fixed length replaces a hash map. Each visit raises the slot for that value by one. When the slot equals k, that value is returned at once. If the scan ends without any slot hitting k, the answer is -1.

Algorithm

1Allocate a frequency array large enough for every allowed value.
2For each entry in order, raise its frequency by one.
3Return that entry as soon as its frequency equals k.
4Return -1 when the scan finishes without a hit.

Example Walkthrough

Input: arr = [1, 7, 4, 3, 4, 8, 7], k = 2

1. The first four values each appear once, so nothing returns yet.
2. The second 4 raises the count of 4 to 2, which equals k, so 4 is returned.
3. The later second 7 also reaches two occurrences, but it appears after 4 already answered.

Output: 4

Common Pitfalls

• Return at the moment the count hits k. Waiting until the full array is tallied can pick a later value.
• When k equals 1, the first array entry is always the answer.
• A value that appears fewer than k times must not be returned, even if it is the most frequent overall.
• The value range is fixed, so the frequency array uses constant extra space relative to that range.

At Least K Occurrences.java

Java

// Approach: Scan left to right and raise a frequency slot for each value. The
// first value whose count hits k is the answer, because that is the earliest
// k-th occurrence. Values lie in 0 through 10^6, so a plain array replaces a
// hash map.
// Complexity: O(n) time, O(1) extra space relative to the fixed value range.
class Solution {
    public int firstElementKTime(int[] arr, int k) {
        int[] cnt = new int[1_000_001];
        for (int a : arr) {
            if (++cnt[a] == k) {
                return a;
            }
        }
        return -1;
    }
}

Was this solution helpful?