Compile Ready
Module 5 · Advanced Sliding Window

Subarrays with K Different Integers

HardProblem 11 of 17 10 min read ~28 min to solve LeetCode
Sliding WindowVariable WindowHash MapCountingAt Most Trick
Asked atGoogleAmazonMicrosoftMetaApple

Problem Statement

Given an integer array nums and an integer k, return the number of contiguous subarrays that contain exactly k distinct integers.

Input

An integer array nums and an integer k, the exact number of distinct values a valid subarray must contain.

Output

An integer: the count of contiguous subarrays whose distinct-value count is exactly k.

Constraints

  • •1 <= nums.length <= 2 * 10^4
  • •1 <= nums[i], k <= nums.length

Examples

Example 1

Input: 
nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: The valid 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
Explanation: The valid subarrays are **[1,2,1,3]**, **[2,1,3]**, and **[1,3,4]**.

Example 3

Input: 
nums = [1,1,1], k = 1
Output: 6
Explanation: Every non-empty subarray contains exactly one distinct value, so the answer is **3 * 4 / 2 = 6**.

Learning Objectives

  • Recognise exact distinct-count subarray questions as candidates for **exactly(K) = atMost(K) - atMost(K - 1)**.
  • Maintain a variable window with a frequency map and a bounded number of distinct values.
  • Explain why every valid at-most window ending at **right** contributes **right - left + 1** subarrays.
  • Convert an exact requirement into two monotone at-most counting passes.

Intuition

Pattern Identification

The phrase exactly k distinct values is the trap. A window with exactly k distinct values is not monotone: after you extend the right edge, it may become invalid, and after you shrink the left edge it may become valid again, but counting only exact windows directly is awkward.

The monotone version is at most k distinct values. If a window ending at right has at most k distinct values, every suffix of that window also has at most k distinct values. That gives the reusable identity exactly(K) = atMost(K) - atMost(K - 1). Count all subarrays with at most k distinct values, subtract those with at most k - 1, and what remains are the subarrays with exactly k distinct values.

Common mistakes

  • ×Trying to count exact windows directly and adding only one when the window has exactly **k** distinct values.
  • ×Forgetting that each valid at-most window ending at **right** contributes **right - left + 1** subarrays, not just one.
  • ×Decrementing a frequency to zero but leaving the key in the map, so the distinct count is wrong.
  • ×Using a fixed-size window even though the subarray length is unrestricted.

Algorithm Explanation

Window setup

Build a helper atMost(limit). It stores a frequency map for values inside nums[left..right]. The invariant is that the map contains at most limit distinct keys. When adding nums[right] creates too many distinct values, move left forward and decrease frequencies until the invariant is restored.

Window visualization

For nums = [1,2,1,2,3] and limit = 2, when right = 3, the valid window is [1,2,1,2] from indices 0..3. Every suffix ending at index 3 is valid: [2], [1,2], [2,1,2], and [1,2,1,2]. That is right - left + 1 = 4 new subarrays. When right = 4 adds 3, the window has three distinct values, so left advances until only [2,3] remains. Now this right edge adds 2 valid subarrays.

Algorithm

  1. Write atMost(limit) and return 0 immediately when limit < 0.
  2. Initialise left = 0, an empty frequency map, and total = 0.
  3. Expand right across the array, adding the new value to the frequency map.
  4. While the map has more than limit keys, remove nums[left] from the map and advance left.
  5. After the window is valid, add right - left + 1 because every suffix of the valid window ending at right is valid.
  6. Return atMost(k) - atMost(k - 1).

Solutions

Solution: At-most difference with frequency map

The exact requirement is handled by subtraction. The helper counts subarrays with at most a given number of distinct values using a standard variable window. Because at-most validity is preserved by taking suffixes, each right edge contributes all starts from left through right.

Step-by-step

  1. Compute atMost(nums, k) and atMost(nums, k - 1).
  2. In the helper, add nums[right] to the frequency map.
  3. If the number of keys exceeds the limit, move left forward and delete keys whose frequency drops to zero.
  4. Once the invariant is restored, add right - left + 1 to the helper answer.
  5. Subtract the two helper counts to isolate subarrays with exactly k distinct values.
Time

O(n)

Space

O(k)

Each helper pass moves left and right forward at most n times. The map stores at most k plus one distinct values during shrinking.

Java implementation

Loading…

Dry Run

Sample input

nums = [1,2,1,2,3], k = 2. Count atMost(2) and atMost(1), then subtract them to get exactly 2 distinct values.

phaserightvalueleft after shrinkwindow statesubarrays addedrunning countmeaning
atMost(2)010{1:1}11[1]
atMost(2)120{1:1, 2:1}23[2], [1,2]
atMost(2)210{1:2, 2:1}36three valid suffixes
atMost(2)320{1:2, 2:2}410four valid suffixes
atMost(2)433{2:1, 3:1}212shrink past the extra distinct value
atMost(1)010{1:1}11single value only
atMost(1)121{2:1}12shrink away 1
atMost(1)212{1:1}13shrink away 2
atMost(1)323{2:1}14shrink away 1
atMost(1)434{3:1}15shrink away 2

The helper counts are atMost(2) = 12 and atMost(1) = 5. Their difference is 7, which is the number of subarrays with exactly 2 distinct integers.

Interview Tips

Lead with the identity exactly(K) = atMost(K) - atMost(K - 1). Then justify why atMost is easy: once the window has at most K distinct values, all suffixes ending at the current right edge are also valid. Interviewers look for that counting jump; without it, candidates often write a complicated exact-window loop.

Likely follow-ups

  • How would the helper change if values were small enough to use an array instead of a hash map?
  • How would you count subarrays with exactly **k** odd numbers?
  • How would you count subarrays with at most **k** distinct values and also return one longest example?
  • Why does the exact trick work for counts but not directly for longest-window answers?

Similar Problems

Binary Subarrays With Sum
MediumUses the same at-most subtraction idea on a binary sum.
Count Number of Nice Subarrays
MediumMaps odd numbers to ones and reuses the exact-count template.
Fruit Into Baskets
MediumMaintains a window with at most two distinct values, but asks for maximum length.
Minimum Window Substring
HardAnother frequency-map window with a tighter validity invariant.

Key Takeaways

  • Exact distinct-count windows become simple when rewritten as two at-most counts.
  • For at-most counting, a valid window ending at **right** contributes **right - left + 1** subarrays.
  • Deleting zero-frequency keys is required to keep the distinct count accurate.
  • The two-pointer movement is linear because **left** and **right** only move forward.
Reusable template: Count exact-K subarrays by computing atMost(K) and subtracting atMost(K - 1), where each valid at-most window contributes all of its suffixes ending at right.