DSA interview question

Subarrays with K Different Integers

Medium · Algorithms · Topics: sliding window, hash map, array

The problem

A playlist analytics job counts contiguous stretches of songs that feature exactly k different artists (each value is an artist ID). "Exactly k" is hard to maintain with one window: from a valid window, extending or shrinking can keep the count at k in many ways. "At most k" is easy, and it counts every valid start for each right end. So the answer is atMost(k) − atMost(k − 1).

Example: [1, 2, 1, 2, 3], k = 2 → 7.

Function signature

long long subarraysWithKDistinct(const vector<int>& nums, int k);

Test cases

Input `(nums, k)`	Output	Explanation
`([1, 2, 1, 2, 3], 2)`	`7`	[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
`([1, 2, 1, 3, 4], 3)`	`3`	[1,2,1,3], [2,1,3], [1,3,4]
`([1, 1, 1], 1)`	`6`	Every subarray
`([1, 2, 3], 3)`	`1`
`([1, 2], 3)`	`0`

(Confirm: exactly k distinct values; subarrays are contiguous and non-empty; the count can be large, so use 64-bit.)

How interviewers phrase it

"Given an integer array nums and an integer k, return the number of good subarrays, where a good subarray has exactly k different integers" (LeetCode 992).

Clarifying questions to ask

Exactly k? (Yes.)
What's the value range? (Values ≤ n, so an array works for counts.)
How large is n? (Up to 2·10⁴; O(n) is expected.)

Follow-ups to expect

"Why is 'exactly k' hard for one window?"
"How does atMost count subarrays?"
"One-pass alternative?"
"Where else does this trick apply?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview