Find shortest subarray with at least k distinct

Q: Find shortest subarray with at least k distinct

This question evaluates proficiency in array manipulation, frequency counting, and efficient tracking of distinct values within contiguous subarrays, measuring algorithmic problem-solving and data-structure usage.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

Given an integer array nums and an integer k, find the length of the shortest contiguous subarray that contains at least k distinct integers.

Task

Return the minimum length of such a subarray. If no subarray contains at least k distinct integers, return -1.

Input/Output

Input: nums (length n ), integer k
Output: integer (minimum length or -1 )

Constraints (reasonable interview assumptions)

1 <= n <= 2*10^5
1 <= k <= n
nums[i] fits in 32-bit signed integer

Examples

nums = [1,2,1,3,4], k = 3 → answer 3 (e.g., [2,1,3] )
nums = [1,1,1], k = 2 → answer -1