The O(n) Club: Conquer Subarrays with Exactly K Distinct Integers (Before Coffee Runs Out)

The O(n) Club: Conquer Subarrays with Exactly K Distinct Integers (Before Coffee Runs Out)

⚡ TL;DR

Counting subarrays with exactly K distinct integers feels like a game of Tetris where every block is a number and your time complexity is about to crash. Forget O(N³); do this instead:

// Classic interview trick!
int result = atMostK(nums, K) - atMostK(nums, K - 1);

🧠 How Devs Usually Mess This Up

Honestly, if I had a buck for every time a developer mixed up subarray vs. subsequence, I’d buy the company. This problem is about contiguous regions only–no leaping around! Typical slip-ups:

• Nesting three loops and hoping your laptop doesn’t catch fire (O(N³) = sad times).
• Missing the “subtract atMostK-1” trick: counting only at most K includes too many snoozy subarrays.
• Punting on hashmap bookkeeping and then wondering why your K-count is drifting into the Twilight Zone.

🔍 What’s Actually Going On

Imagine the array is a sushi conveyor: you want plates with exactly K types of sushi, no more, no less. Instead of picking every combo (chef cries), you:

• Count all plates with at most K types. (Still lots…)
• Count plates with at most K-1 types. (The stuff that’s too plain.)
• Subtract: all the “Goldilocks” plates have exactly K types. Math: atMostK – atMostK-1.

And you slide this window using two pointers plus a frequency map, so you only ever touch each plate (number) once.

🛠️ PseudoCode

• Define atMostK(arr, k) to count subarrays with at most K ballpark flavors.
  • Keep a left pointer and expand right through the array.
  • On each new number to the right, bump up its counter in your map.
  • If the map goes over K keys, increment left and shrink until you’re back at or under K.
  • Every step, add right-left+1 (the # of valid subarrays ending at right).
• Return atMostK(nums, K) - atMostK(nums, K-1) for the final answer.

💻 The Code

public int subarraysWithKDistinct(int[] nums, int K) {
    return atMostK(nums, K) - atMostK(nums, K - 1);
}
 private int atMostK(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    int result = 0, left = 0;
    for (int right = 0; right < nums.length; right++) {
        map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
        if (map.get(nums[right]) == 1) k--;
        while (k < 0) {
            map.put(nums[left], map.get(nums[left]) - 1);
            if (map.get(nums[left]) == 0) k++;
            left++;
        }
        result += right - left + 1;
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• K = 0? Congrats: nothing is ever exactly zero types of anything (result is zero).
• Array shorter than K? Sorry, there cannot be enough unique values to bother.
• Remember to decrement as you pop elements off the left; frequencies matter!
• Runtime: O(N), Space: O(N). The hashmap won’t throw a birthday party but it gets the job done.

🧠 Interviewer Brain-Tattoo

When a sliding window question wants exactly K of something, don’t brute force—just “window minus window.” Or, as Chandler would say, “Could this trick be any more interview-worthy?” 😏