Katkat
Back

Find minimum subarray length with k distinct integers

IBMSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests proficiency with the sliding window technique and hash map-based frequency tracking, applied to subarray problems requiring exact cardinality constraints. It assesses the ability to distinguish between "exactly k distinct" and "at most k distinct" variants — a nuance that reveals depth in algorithmic thinking commonly evaluated in software engineering interviews.

Given an integer array arr and an integer k, find the minimum length of a contiguous subarray that contains exactly k distinct integer values.

Return the minimum length, or -1 if no such subarray exists.

Constraints & Assumptions

  • arr can contain duplicate values; values may be any integers (positive, negative, or zero).
  • A subarray is a contiguous slice of the array — not a subsequence.
  • "Exactly k distinct" means the set of distinct values inside the window has cardinality exactly k.
  • Aim for $O(n)$ time and $O(n)$ extra space, where $n$ is the length of arr.

Clarifying Questions to Ask

  • What should be returned when k = 0 or when k exceeds the total number of distinct values in arr? (Likely -1, since no qualifying subarray exists.)
  • Can arr be empty? What is the expected return in that case?
  • Is k guaranteed to be non-negative, and can it be larger than len(arr)?
  • Should the answer count a single qualifying window, or is there any tie-breaking requirement beyond "minimum length"?

Hints

Hint 1

Where to start: Think about a single pass with a **sliding window** plus a hash map from value → count inside the window. The number of map keys is the number of distinct values currently in the window.

Hint 2

The "exactly k" trap: "At least `k` distinct" is the easy variant. For **exactly `k`**, once the window holds `k` distinct values, keep shrinking from the left: you can safely drop the leftmost element as long as it's a *duplicate* (its count in the window stays $\geq 1$ after removal). Stop shrinking the moment removing the left element would drop a distinct value (count would hit $0$), then record the window length.

Hint 3

Pitfall: When you grow the window and the distinct count exceeds `k`, that window can never be salvaged by adding more elements — you must advance the left pointer until distinct $\leq k$ again. Don't measure length while distinct is $\neq k$.

Follow-up questions

  • How would you adapt the solution to return the **count of all** subarrays with exactly `k` distinct integers, rather than the minimum length? (Hint: `exactly(k) = atMost(k) − atMost(k−1)`.)
  • If you instead needed the **maximum length** subarray with exactly `k` distinct, how would the shrink condition change?
  • Suppose the array is a **stream** you can only read once and cannot store fully — what part of this approach breaks, and what would you do?
  • How would you handle the variant "exactly `k` distinct **and** every value appears at least `m` times"?