NeetCode #256LC-992HardSliding Window
← Back to All Problems#256 · #992 · Subarrays with K Different Integers(K 个不同整数的子数组)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the number of good subarrays: contiguous subarrays with exactly k different integers. Constraints: 1 <= nums.length <= 2 * 10^4, 1 <= nums[i], k <= nums.length.💡 Core Algorithmic Approaches
- The "exactly k" count decomposes as
atMost(k) - atMost(k - 1). atMost(g)is a sliding window with at mostgdistinct values, contributingr - l + 1subarrays per right endpoint.- When shrinking, delete keys whose count reaches zero so the distinct count stays accurate.
- The answer is the difference of the two counts.
💻 Benchmark Python3 Implementation
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
from collections import defaultdict
def atMost(g: int) -> int:
if g <= 0:
return 0
cnt = defaultdict(int)
l = 0
res = 0
for r, x in enumerate(nums):
cnt[x] += 1
while len(cnt) > g: # too many distinct values
cnt[nums[l]] -= 1
if cnt[nums[l]] == 0:
del cnt[nums[l]]
l += 1
res += r - l + 1
return res
return atMost(k) - atMost(k - 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two linear passes, since each pointer moves monotonically within each call.
💾 Space Complexity
O(n) for the frequency maps.
⚠️ Interview Pitfalls & Follow-ups
- Using one window with two left pointers: possible, but the two-pass formulation is far easier to get right.
- Not deleting zero-count keys:
len(cnt)would be wrong. - Forgetting the
g <= 0guard:atMost(0)must be 0, and the window logic would otherwise allow empty windows incorrectly. - Confusing "exactly k distinct" with "at most k distinct": the problem asks for exactly
k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner