Count Subarrays With K Distinct Integers - Video Solutions

Problem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays contain exactly k distinct integers. The challenge is efficiently tracking unique elements while expanding and shrinking subarray boundaries.

Approach 1: Brute Force with Set Tracking (O(n²) time, O(n) space)

Start every subarray from index i. Extend the right boundary one element at a time and track unique numbers using a set or hash map. Each extension updates the number of distinct elements. When the count becomes exactly k, increment the result. Stop extending once the count exceeds k. This approach checks all possible starting positions, which leads to quadratic time complexity. Useful for understanding the problem but too slow for large inputs.

Approach 2: Sliding Window with At-Most Trick (O(n) time, O(n) space)

The key observation: counting subarrays with exactly k distinct elements can be reduced to counting subarrays with at most k distinct elements. The formula is:

exactly(k) = atMost(k) - atMost(k-1)

Implement a sliding window using two pointers and a frequency hash table. Expand the right pointer and update counts. When distinct elements exceed k, shrink the left pointer until the window becomes valid again. For each valid position, add the window length contribution (right - left + 1). This counts all subarrays ending at right that satisfy the constraint.

The helper function atMost(k) runs once for k and once for k-1. Each element enters and leaves the window at most once, giving linear complexity. This technique is a classic pattern combining sliding window with frequency counting on an array.

Approach 3: Sliding Window with Two Left Pointers (O(n) time, O(n) space)

Another optimized strategy maintains two sliding windows simultaneously: one tracking at most k distinct elements and another tracking at most k-1. Both windows expand with the same right pointer but shrink independently. The difference between their valid starting indices directly gives the number of subarrays ending at the current index with exactly k distinct elements. This avoids calling a helper function twice but follows the same underlying logic.

Recommended for interviews: The sliding window atMost(k) - atMost(k-1) technique is the expected solution. It demonstrates strong understanding of window invariants, frequency maps, and counting strategies. Brute force shows baseline reasoning, but the linear sliding window solution is what interviewers want to see for hard array problems.