Subarrays with K Different Integers

How it works

This approach simplifies the previous one by using a single left pointer and a counter cnt to track how many positions we can extend the left boundary. When we have exactly k distinct values, we shrink the window from the left as long as the leftmost element has duplicates, incrementing cnt each time. The number of valid subarrays ending at the current position is cnt + 1.

Steps

1. Create an array count of size n + 1 for frequency tracking (since values are in range [1, n]).
2. Initialize l, cnt, and res to 0.
3. For each right pointer r:
   • Increment count[nums[r]]. If this is a new distinct value, decrement k.
   • If k < 0 (more than k distinct), decrement count[nums[l]], increment l, increment k, and reset cnt = 0.
   • If k == 0 (exactly k distinct), shrink from the left while count[nums[l]] > 1, incrementing cnt each time.
   • Add cnt + 1 to res.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Trying to Count Exactly K Directly with a Single Sliding Window

A single sliding window can only count subarrays with "at most k" distinct values, not "exactly k." To count exactly k, you must use the formula atMostK(k) - atMostK(k-1) or maintain two pointers to track a range of valid left boundaries.

Off-by-One Errors in Subarray Counting

When counting subarrays ending at position r, the count is r - l + 1, not r - l. This represents all subarrays starting at any position from l to r and ending at r. Forgetting the +1 leads to undercounting.

Not Properly Tracking When Distinct Count Changes

When a new element is added, increment the distinct count only if its frequency becomes 1 (first occurrence). When removing, decrement the distinct count only when its frequency drops to 0. Using set size directly on every operation is less efficient and error-prone.

Resetting State Incorrectly in the One-Pass Approach

In the one-pass sliding window variant, when the distinct count exceeds k, you must reset the accumulated count cnt to 0. Forgetting this reset causes the algorithm to incorrectly carry over counts from invalid window states.

Confusing the Two Left Pointers in One-Pass Solutions

The one-pass approach uses two left pointers: l_far (leftmost valid start) and l_near (rightmost valid start where the leftmost element appears exactly once). Mixing up their roles or forgetting to update l_far = l_near when shrinking past k distinct values produces incorrect results.

from typing import List

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        res = l = cnt = 0

        for r in range(n):
            count[nums[r]] += 1
            if count[nums[r]] == 1:
                k -= 1

            if k < 0:
                count[nums[l]] -= 1
                l += 1
                k += 1
                cnt = 0

            if k == 0:
                while count[nums[l]] > 1:
                    count[nums[l]] -= 1
                    l += 1
                    cnt += 1

                res += (cnt + 1)

        return res

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> count(n + 1, 0);
        int res = 0, l = 0, cnt = 0;

        for (int r = 0; r < n; r++) {
            count[nums[r]]++;
            if (count[nums[r]] == 1) {
                k--;
            }

            if (k < 0) {
                count[nums[l]]--;
                l++;
                k++;
                cnt = 0;
            }

            if (k == 0) {
                while (count[nums[l]] > 1) {
                    count[nums[l]]--;
                    l++;
                    cnt++;
                }

                res += (cnt + 1);
            }
        }

        return res;
    }
};