Katkat
Back

Shortest Subarray with at Least K Distinct Values

SquarepointQuantitative Researcher · Technical Screen
MediumQuantitative ResearcherTechnical ScreenCoding & Algorithms

Last updated

Determine the minimum length of a contiguous subarray that contains at least k distinct elements. This problem tests sliding-window techniques, hash map management, and linear-time optimization.

Shortest Subarray with at Least K Distinct Values

You are given an array of positive integers nums and a positive integer k.

A subarray is called valid if it contains at least k distinct integers.

Write a function to return the minimum length of a valid contiguous subarray. If no such subarray exists, return -1.

Function Signature

def min_subarray_len_k_distinct(nums: list[int], k: int) -> int:
    pass

Constraints

  • 1 <= len(nums) <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^5

Examples

Example 1:

Input: nums = [1, 2, 1, 2, 3], k = 3
Output: 3
Explanation: The subarray [1, 2, 3] from index 2 to 4 contains 3 distinct values {1, 2, 3} and has length 3. No subarray of length 1 or 2 contains 3 distinct values.

Example 2:

Input: nums = [2, 1, 3, 2, 4], k = 4
Output: 4
Explanation: The subarray [1, 3, 2, 4] contains 4 distinct values and has length 4.

Example 3:

Input: nums = [1, 1, 1], k = 2
Output: -1
Explanation: There is only 1 distinct integer in the entire array, so it is impossible to find a subarray with at least 2 distinct values.

Edge Cases to Consider

  • k = 1: Any single element has 1 distinct value, so the answer should always be 1 (if len(nums) >= 1).
  • k > len(nums): Impossible to satisfy, immediately return -1.
  • nums has fewer than k unique elements across the whole array: return -1.

Hints

Hint 1

Notice that if a subarray nums[left:right+1] has at least k distinct elements, expanding it to the right cannot decrease the count of distinct elements.

Hint 2

Use a two-pointer sliding window and maintain a frequency map of the elements currently in the window.

Hint 3

Whenever the window has at least k distinct elements, try shrinking it from the left while maintaining the condition, updating your minimum length at each valid step.

Follow-up questions

  • How would your approach change if you needed to count the total number of subarrays containing at least k distinct values?
  • Can you solve this problem with O(1) auxiliary space if the values in nums are strictly bounded within [1, n]?
  • How would you adapt the solution for a streaming data model where elements arrive one by one and window queries must be answered with low latency?