2Brute2Best
🔥0

Subarrays with K Different Integers

Hard·LeetCode #992 Pro OnlySlight Variation
LeetCode
01

Problem Statement

You are given an integer array nums and a number k.

Call a contiguous subarray good if it contains exactly k different values. For example, [1, 2, 3, 1, 2] has 3 different values: 1, 2 and 3.

Count the good subarrays.

Input

An integer array nums and an integer k.

Output

The number of contiguous subarrays with exactly k distinct values.

Example 1
Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 7

The good subarrays are [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2].

Example 2
Input: nums = [1, 2, 1, 3, 4], k = 3
Output: 3

The good subarrays are [1,2,1,3], [2,1,3] and [1,3,4].

Constraints
  • • 1 ≤ nums.length ≤ 2 · 10^4
  • • 1 ≤ nums[i] ≤ nums.length
  • • 1 ≤ k ≤ nums.length
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“contiguous subarray”
→ Counting ranges → window.
“exactly k different values”
→ "Exactly" → two at-most counts. "Different values" → count map + distinct counter.
“count the subarrays”
→ Each right end adds `right − left + 1`.
03

Approach Complexity Ladder

Brute Force — try every startO(N²)O(N)

Fix each start, grow the end with a count map, count when distinct = k

Optimal — atMost(k) − atMost(k − 1) with count mapsO(N)O(N)

Two at-most-k-distinct windows; subtract

Brute Force Intuition

For every start, move the end right and keep a count of each value. Track how many different values there are. Count one whenever it equals k, and stop once it goes above k (it can never come back down for this start).

Recognition rule for this sub-pattern:

"Exactly K" is not monotonic, so a window can't count it directly. Use exactly(K) = atMost(K) − atMost(K − 1).
Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track
C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track
Count Number of Nice SubarraysCount Subarrays With Fixed Bounds