AlgoInsight

DSA problem

Subarrays with K Different Integers

HardSliding Window - Dynamic SizePattern: Sliding Window (at-most-k trick)top600AmazonGoogleMetaMicrosoft

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good subarray is a contiguous subarray where the number of distinct integers in that subarray is exactly equal to k.

For example, [1, 2, 3, 1, 2] has exactly 3 distinct integers. A subarray is a contiguous, non-empty part of an array.

Counting subarrays with exactly k distinct integers directly is awkward because the constraint is not monotonic. The standard trick rewrites the answer as atMost(k) - atMost(k - 1), where atMost(x) counts subarrays with at most x distinct integers — a quantity that is monotonic and computable with a single linear sliding window.

Examples

Example 1
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2
Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Example 3
Input: nums = [2,2,2], k = 1
Output: 6
Explanation: Every non-empty subarray has exactly 1 distinct integer; there are 6 such subarrays.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowarrayhash-tablecounting

Browse all DSA problems