⚡Flashcard Drill➔
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

  1. The "exactly k" count decomposes as atMost(k) - atMost(k - 1).
  2. atMost(g) is a sliding window with at most g distinct values, contributing r - l + 1 subarrays per right endpoint.
  3. When shrinking, delete keys whose count reaches zero so the distinct count stays accurate.
  4. 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 <= 0 guard: 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems