L11. Subarray with K Different Integers | 2 Pointers and Sliding Window

This chapter covers an advanced algorithmic problem from the Two Pointer and Sliding Window pattern: counting subarrays that contain exactly $K$ distinct integers. We will examine why a naive brute-force approach fails, analyze the limitations of a direct two-pointer strategy, formulate a clever mathematical transformation (using At Most $K$ minus At Most $K-1$), and implement an optimal $O(N)$ solution.

1. Defining the Problem: Exactly K Different Integers

Given an array of integers and an integer $K$, your task is to return the count of subarrays (contiguous portions of the array) that contain exactly $K$ distinct (different) integers.

Example Scenario

Consider an array with values and $K = 3$:

• If a subarray has 2 distinct integers, it cannot be counted.
• If a subarray has 4 distinct integers, it cannot be counted.
• If a subarray has exactly 3 distinct integers, it must be counted and added to our total answer.

2. Why the Naive Brute-Force Approach Fails

The most intuitive brute-force strategy is to generate every possible contiguous subarray, track the distinct elements using a hash map, and increment a counter if the map size equals $K$.

Naive Algorithm Logic

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(N^2)$ or $\mathcal{O}(N^2 \log N)$ if hashing operations take logarithmic time.
• Space Complexity: $\mathcal{O}(N)$ in the worst-case scenario where all elements are unique and stored in the map.

Note: An $\mathcal{O}(N^2)$ solution is typically too slow for large constraint ranges (e.g., $N = 10^5$) in coding interviews. The interviewer will expect an optimal $\mathcal{O}(N)$ approach.

3. The Two-Pointer Sliding Window Dilemma

Since the problem deals with subarrays and requires an optimal linear time complexity ($\mathcal{O}(N)$), a Two-Pointer / Sliding Window approach is naturally indicated. However, this is not a standard longest-subarray problem.

Where Standard Sliding Window Fails Here

If we maintain left (L) and right (R) pointers and expand R while managing a frequency map:

1. When the distinct element count equals $K$, we record a valid subarray and expand R.
2. When the count exceeds $K$, we shrink the window from the left (L) until the count drops back to $K$ or below.

Array:  [2, 1, 1, 3, 4]  (K = 3)
         L     R
         (Window expands, then shrinks when elements > K)

The Pitfall: As R moves forward and we perform window adjustments, we inevitably lose track of valid sub-configurations. Because exact-match conditions are volatile under window expansions and contractions, a direct single-pass sliding window for exact $K$ fails to reliably capture every valid inner permutation.

4. Transforming the Problem: "At Most K" Mental Model

To bypass the exact-match dilemma, we can reframe the problem using a fundamental set-theory equivalence:

Why This Works

• At Most $K$: Counts all subarrays that have $1, 2, 3, \dots, K$ distinct integers.
• At Most $K-1$: Counts all subarrays that have $1, 2, 3, \dots, K-1$ distinct integers.
• Subtracting the latter from the former filters out everything with fewer than $K$ integers, leaving strictly subarrays with exactly $K$ integers.

5. Solving the Helper Function: Subarrays with "At Most K" Distinct Integers

Let's design a helper function, helper(nums, K), that returns the total number of subarrays containing at most $K$ distinct integers.

Mental Model & Mechanics

1. Initialize L = 0, R = 0, count = 0, and a frequency map.
2. Expand R across the array, adding nums[R] to the map.
3. If the map size exceeds $K$, shrink the window from the left (L) until map.size() <= K.
4. For every valid window position from L to R, the number of valid subarrays ending at R and starting anywhere between L and R is given by the formula:

Real-Life Analogy: Expanding Elastic Bands

Imagine holding a rubber band at index L and stretching it to R. As long as the number of unique items inside the band doesn't exceed $K$, every possible smaller band formed by sliding L up to the current position is also valid. The length (R - L + 1) gives you the exact count of all those valid sub-bands created by adding the new element at R.

6. Step-by-Step Code Walkthrough

Below is the complete implementation incorporating the helper function and the subtraction logic.

function subarraysWithKDistinct(nums: number[], k: number): number {
    return helper(nums, k) - helper(nums, k - 1);
}

function helper(nums: number[], k: number): number {
    if (k < 0) return 0;
    
    let l = 0;
    let r = 0;
    let count = 0;
    const map = new Map<number, number>();
    const n = nums.length;

    while (r < n) {
        // 1. Expand the window by including nums[r]
        map.set(nums[r], (map.get(nums[r]) || 0) + 1);

        // 2. Shrink the window if distinct elements exceed k
        while (map.size > k) {
            let leftVal = nums[l];
            map.set(leftVal, map.get(leftVal)! - 1);
            if (map.get(leftVal) === 0) {
                map.delete(leftVal);
            }
            l++;
        }

        // 3. Add all valid subarrays ending at r
        count += (r - l + 1);
        r++;
    }

    return count;
}

Flow Execution Example

7. Complexity Analysis of the Optimal Solution

8. Summary and Key Takeaways

• Exact Match Transformation: When a direct two-pointer approach fails for exact counts, transform the problem into AtMost(K) - AtMost(K - 1).
• Sliding Window Invariant: For "At Most $K$" problems, whenever the window size exceeds $K$, shrink from the left until the invariant is restored.
• Counting Subarrays: In a valid window from L to R, the number of valid subarrays ending at R is precisely equal to the window length: R - L + 1.
• Map Management: Always decrement frequencies and explicitly delete keys from your hash map when frequencies hit zero to maintain an accurate distinct element count (map.size).
• Optimal Efficiency: By avoiding nested brute-force loops, the sliding window reduces time complexity from quadratic $\mathcal{O}(N^2)$ to linear $\mathcal{O}(N)$.