Practice Google Coding Question | Real Coding Interviews

Quick Summary

Find the length of the shortest contiguous subarray containing at least k distinct integers.
Dynamically adjust the window boundaries to maintain the distinct count constraint.
Return -1 if the entire array lacks enough unique elements to form a valid subarray.

What This Tests

Dynamic window management with two pointers
Frequency tracking using hash maps or fixed-size arrays
Optimizing beyond brute-force range checking
Edge case handling for minimal windows and duplicate-heavy inputs

Common Patterns

Sliding Window

Two Pointers

Hashing

(This question is a variation of the LeetCode question 992. Subarrays with K Different Integers. If you haven't completed that question yet, it is recommended to solve it first.)

Given an integer array arr and an integer k, a subarray is called good if it contains at least k distinct integers. Return the length of the shortest good subarray. If no good subarray exists, return -1.

Constraints:

1 ≤ arr.length ≤ $10^5$
1 ≤ arr[i] ≤ $10^5$
1 ≤ k ≤ arr.length

Test Cases

Input

Output

Expected