# Subarrays with K Different Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/subarrays-with-k-different-integers)
Canonical: https://scaleengineer.com/dsa/problems/subarrays-with-k-different-integers
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Roblox](https://scaleengineer.com/companies/roblox)
---
## Problem
Given an integer array `nums` and an integer `k`, return _the number of **good subarrays** of_ `nums`.

A **good array** is an array where the number of different integers in that array is exactly `k`.

* For example, `[1,2,3,1,2]` has `3` different integers: `1`, `2`, and `3`.

A **subarray** is a **contiguous** part of an array.

**Example 1:**

**Input:** nums = [1,2,1,2,3], k = 2
**Output:** 7
**Explanation:** Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

**Example 2:**

**Input:** nums = [1,2,1,3,4], k = 3
**Output:** 3
**Explanation:** Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `1 <= nums[i], k <= nums.length`

# Approaches
## Brute Force
This approach involves checking every possible subarray of the input array `nums`. For each subarray, we count the number of distinct integers it contains. If this count is exactly `k`, we increment our result counter. While straightforward, this method is inefficient for large inputs due to its nested loop structure, leading to a quadratic time complexity.
**Time:** O(N^2). There are two nested loops. The outer loop runs `N` times, and the inner loop runs up to `N` times. The operations inside the inner loop (adding to a `HashSet` and checking its size) take constant time on average. · **Space:** O(k). The `HashSet` used to store distinct elements for a subarray will hold at most `k+1` elements before the inner loop breaks. In the worst case, `k` can be up to `N`, making it O(N).
**Pros:** Simple to understand and implement.; It is a direct translation of the problem statement into code.
**Cons:** Highly inefficient for larger input sizes, likely resulting in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms.; Performs a lot of redundant work by re-calculating the set of distinct elements for overlapping subarrays.
### Explanation
The brute-force method systematically generates all subarrays and verifies the condition for each one. We use two nested loops to define the start (`i`) and end (`j`) of a subarray. For a fixed starting point `i`, we expand the subarray by moving `j` from `i` to the end of the array. To efficiently count distinct elements for the expanding subarray `nums[i...j]`, we use a `HashSet`. As we add `nums[j]` to the set, we check its size. If the size becomes exactly `k`, we've found a 'good' subarray and increment our counter. This process is repeated for all possible starting positions `i`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            Set<Integer> distinctElements = new HashSet<>();
            for (int j = i; j < n; j++) {
                distinctElements.add(nums[j]);
                if (distinctElements.size() == k) {
                    count++;
                } else if (distinctElements.size() > k) {
                    // Optimization: if size exceeds k, no need to check further for this i
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a variable `count` to 0 to store the number of good subarrays.
- Use a nested loop to generate all possible subarrays. The outer loop with index `i` determines the start of the subarray, and the inner loop with index `j` determines the end.
- For each subarray starting at `i`, use a `HashSet` to keep track of the distinct elements encountered as `j` increases.
- In the inner loop, for each element `nums[j]`, add it to the `HashSet`.
- After adding `nums[j]`, check the size of the `HashSet`.
- If `distinctElements.size() == k`, it means the current subarray `nums[i...j]` has exactly `k` distinct elements, so we increment `count`.
- An optional optimization: If `distinctElements.size() > k`, we can break the inner loop because any further extension of this subarray will also have more than `k` distinct elements.
- After iterating through all possible `i` and `j`, return the final `count`.

## Sliding Window with "At Most K" Subarrays
A direct sliding window approach for "exactly k" is complex because a valid window `[left, right]` can contain multiple valid subarrays, and the count isn't straightforward. A more elegant and efficient solution uses a clever insight: the number of subarrays with *exactly* `k` distinct elements is the same as (the number of subarrays with *at most* `k` distinct elements) minus (the number of subarrays with *at most* `k-1` distinct elements). This transforms the problem into two simpler subproblems, each solvable efficiently using a standard sliding window technique.
**Time:** O(N). The `atMostK` function is called twice. In each call, both the `left` and `right` pointers traverse the array at most once. Thus, the total time complexity is O(N) + O(N) = O(N). · **Space:** O(k). The `HashMap` stores at most `k+1` distinct elements before shrinking. In the worst case, `k` can be up to `N`, making the space complexity O(N).
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Demonstrates a powerful and reusable problem-solving pattern for 'exactly k' type problems.; The sliding window avoids re-computation by efficiently updating the window state in O(1) amortized time.
**Cons:** The logic of `exactly(k) = atMost(k) - atMost(k-1)` might not be immediately obvious.; Requires implementing a helper function, which adds a bit of structural complexity to the code.
### Explanation
This approach reframes the problem. Instead of counting subarrays with exactly `k` distinct elements directly, we count subarrays with *at most* `k` distinct elements. Let's call this function `atMostK(k)`. The final answer is then `atMostK(k) - atMostK(k-1)`.

The `atMostK` function is implemented using a sliding window. We maintain a window `[left, right]` and a frequency map of elements within it. We expand the window by moving `right`. If at any point the number of distinct elements in the window exceeds `k`, we shrink the window from the left by moving `left` forward until the window is valid again. For every valid window `[left, right]`, any subarray that ends at `right` and starts within this window (from `left` to `right`) will also have at most `k` distinct elements. The number of such subarrays is `right - left + 1`. By summing this value for each position of `right`, we get the total count for `atMostK`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // exactly(k) = atMost(k) - atMost(k-1)
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }

    /**
     * Helper function to count the number of subarrays with at most K distinct integers.
     */
    private int atMostK(int[] nums, int k) {
        int count = 0;
        int left = 0;
        Map<Integer, Integer> freq = new HashMap<>();

        for (int right = 0; right < nums.length; right++) {
            // Add the rightmost element to the window
            freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);

            // If the window is invalid (more than k distinct elements), shrink it from the left
            while (freq.size() > k) {
                freq.put(nums[left], freq.get(nums[left]) - 1);
                if (freq.get(nums[left]) == 0) {
                    freq.remove(nums[left]);
                }
                left++;
            }

            // The window [left, right] is now valid (at most k distinct elements).
            // All subarrays ending at 'right' and starting within [left, right] are also valid.
            // The number of such subarrays is (right - left + 1).
            count += (right - left + 1);
        }

        return count;
    }
}
```
### Algorithm
- The core idea is that `exactly(k) = atMost(k) - atMost(k-1)`.
- Create a helper function `atMostK(nums, k)` that counts subarrays with at most `k` distinct elements.
- In the main function, calculate `atMostK(nums, k) - atMostK(nums, k - 1)` and return the result.
- **`atMostK` function implementation:**
  - Initialize `count = 0`, `left = 0`, and a frequency map `freq`.
  - Iterate through the array with a `right` pointer from `0` to `n-1`.
  - For each `nums[right]`, add it to the current window and update its count in `freq`.
  - While the number of distinct elements (`freq.size()`) is greater than `k`, shrink the window from the left:
    - Decrement the frequency of `nums[left]`.
    - If the frequency becomes 0, remove the element from the map.
    - Increment `left`.
  - After the window `[left, right]` is valid (has at most `k` distinct elements), all subarrays ending at `right` and starting from an index between `left` and `right` are also valid. The number of such subarrays is `right - left + 1`.
  - Add `right - left + 1` to `count`.
  - After the loop finishes, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int subarraysWithKDistinct(int[] nums, int k) {
    int[] left = f(nums, k);
    int[] right = f(nums, k - 1);
    int ans = 0;
    for (int i = 0; i < nums.length; ++i) {
      ans += right[i] - left[i];
    }
    return ans;
  }
private
  int[] f(int[] nums, int k) {
    int n = nums.length;
    int[] cnt = new int[n + 1];
    int[] pos = new int[n];
    int s = 0;
    for (int i = 0, j = 0; i < n; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++s;
      }
      for (; s > k; ++j) {
        if (--cnt[nums[j]] == 0) {
          --s;
        }
      }
      pos[i] = j;
    }
    return pos;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int subarraysWithKDistinct(vector<int> &nums, int k) {
    vector<int> left = f(nums, k);
    vector<int> right = f(nums, k - 1);
    int ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
      ans += right[i] - left[i];
    }
    return ans;
  }
  vector<int> f(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> pos(n);
    int cnt[n + 1];
    memset(cnt, 0, sizeof(cnt));
    int s = 0;
    for (int i = 0, j = 0; i < n; ++i) {
      if (++cnt[nums[i]] == 1) {
        ++s;
      }
      for (; s > k; ++j) {
        if (--cnt[nums[j]] == 0) {
          --s;
        }
      }
      pos[i] = j;
    }
    return pos;
  }
};

```

### Python

```python
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int: def f(k): pos = [0] * len(nums) cnt = Counter() j = 0 for i, x in enumerate(nums): cnt[x] += 1 while len(cnt) > k: cnt[nums[j]] -= 1 if cnt[nums[j]] == 0: cnt . pop(nums[j]) j += 1 pos[i] = j return pos return sum(a - b for a, b in zip(f(k - 1), f(k)))

```