Subarrays with K Different Integers

Hard

#0946Time: 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).2 companies

Patterns

Sliding Window Counting

Data structures

Array Hash Table

Companies

Morgan Stanley Roblox

Prompt

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 * 10⁴
1 <= nums[i], k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int subarraysWithKDistinct(int[] nums, int k) {6        int count = 0;7        int n = nums.length;8        for (int i = 0; i < n; i++) {9            Set<Integer> distinctElements = new HashSet<>();10            for (int j = i; j < n; j++) {11                distinctElements.add(nums[j]);12                if (distinctElements.size() == k) {13                    count++;14                } else if (distinctElements.size() > k) {15                    // Optimization: if size exceeds k, no need to check further for this i16                    break;17                }18            }19        }20        return count;21    }22}

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int subarraysWithKDistinct(int[] nums, int k) {6        // exactly(k) = atMost(k) - atMost(k-1)7        return atMostK(nums, k) - atMostK(nums, k - 1);8    }9 10    /**11     * Helper function to count the number of subarrays with at most K distinct integers.12     */13    private int atMostK(int[] nums, int k) {14        int count = 0;15        int left = 0;16        Map<Integer, Integer> freq = new HashMap<>();17 18        for (int right = 0; right < nums.length; right++) {19            // Add the rightmost element to the window20            freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);21 22            // If the window is invalid (more than k distinct elements), shrink it from the left23            while (freq.size() > k) {24                freq.put(nums[left], freq.get(nums[left]) - 1);25                if (freq.get(nums[left]) == 0) {26                    freq.remove(nums[left]);27                }28                left++;29            }30 31            // The window [left, right] is now valid (at most k distinct elements).32            // All subarrays ending at 'right' and starting within [left, right] are also valid.33            // The number of such subarrays is (right - left + 1).34            count += (right - left + 1);35        }36 37        return count;38    }39}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int subarraysWithKDistinct(int[] nums, int k) {4    int[] left = f(nums, k);5    int[] right = f(nums, k - 1);6    int ans = 0;7    for (int i = 0; i < nums.length; ++i) {8      ans += right[i] - left[i];9    }10    return ans;11  }12private13  int[] f(int[] nums, int k) {14    int n = nums.length;15    int[] cnt = new int[n + 1];16    int[] pos = new int[n];17    int s = 0;18    for (int i = 0, j = 0; i < n; ++i) {19      if (++cnt[nums[i]] == 1) {20        ++s;21      }22      for (; s > k; ++j) {23        if (--cnt[nums[j]] == 0) {24          --s;25        }26      }27      pos[i] = j;28    }29    return pos;30  }31}

1class Solution {2public:3  int subarraysWithKDistinct(vector<int> &nums, int k) {4    vector<int> left = f(nums, k);5    vector<int> right = f(nums, k - 1);6    int ans = 0;7    for (int i = 0; i < nums.size(); ++i) {8      ans += right[i] - left[i];9    }10    return ans;11  }12  vector<int> f(vector<int> &nums, int k) {13    int n = nums.size();14    vector<int> pos(n);15    int cnt[n + 1];16    memset(cnt, 0, sizeof(cnt));17    int s = 0;18    for (int i = 0, j = 0; i < n; ++i) {19      if (++cnt[nums[i]] == 1) {20        ++s;21      }22      for (; s > k; ++j) {23        if (--cnt[nums[j]] == 0) {24          --s;25        }26      }27      pos[i] = j;28    }29    return pos;30  }31};

1class Solution:2    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)))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem