Subarrays with K Different Integers
Hard · Sliding Window · Array · Hash Table · Sliding Window · Counting
Problem
Given an integer array nums and an integer k, call a contiguous subarray good if it contains exactly k different integers.
Return the number of good subarrays. Subarrays are counted by position, so equal subarrays at different places count separately.
Examples
Input: nums = [1,2,1,3], k = 2 Output: 4
The good subarrays are [1,2], [2,1], [1,3] and [1,2,1].
Input: nums = [3,3,3], k = 1 Output: 6
All 6 subarrays contain only the value 3.
Input: nums = [1,2,2], k = 3 Output: 0
The whole array has only two different values, so no subarray has three.
Constraints
- 1 <= len(nums) <= 2 · 10^4
- 1 <= nums[i], k <= len(nums)
Approaches
- Baseline: every start, stop past k — time O(n²), space O(k)
Follow-up
The same subtraction turns any "exactly" count into two "at most" counts whenever the "at most" version slides: exactly k odd numbers, a binary array summing to exactly a goal, and so on. Both appear as use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
