How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find shortest subarray with ≥k distinct integers

Quick Overview

This question evaluates understanding of array algorithms, handling of distinct-element counting, and the ability to design time- and space-efficient solutions for constrained subarray queries.

Find shortest subarray with ≥k distinct integers

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an integer array `nums` of length `n` and an integer `k`, find the length of the **shortest contiguous subarray** that contains **at least `k` distinct** integers. If no subarray contains at least `k` distinct integers, return `-1`. ### Input - `nums`: array of integers - `k`: integer ### Output - Integer: minimum length, or `-1` ### Constraints (typical) - `1 <= n <= 2*10^5` - `1 <= k <= n` - `|nums[i]| <= 10^9` (An efficient solution is expected; quadratic approaches may time out.)

Quick Answer: This question evaluates understanding of array algorithms, handling of distinct-element counting, and the ability to design time- and space-efficient solutions for constrained subarray queries.

Given an integer array `nums` and an integer `k`, return the length of the shortest contiguous subarray that contains at least `k` distinct integers. A subarray is contiguous, and values are considered distinct by their integer value. If no such subarray exists, return `-1`.

Constraints

1 <= len(nums) <= 2 * 10^5
1 <= k <= len(nums)
-10^9 <= nums[i] <= 10^9

Examples

Input: ([1, 2, 1, 3, 4], 3)

Expected Output: 3

Explanation: The shortest valid subarrays are [2, 1, 3] and [1, 3, 4], both of length 3.

Input: ([1, 1, 1], 2)

Expected Output: -1

Explanation: There is only 1 distinct integer in the entire array, so reaching 2 distinct integers is impossible.

Input: ([5, 5, 5, 5], 1)

Expected Output: 1

Explanation: Any single-element subarray already contains at least 1 distinct integer.

Input: ([], 1)

Expected Output: -1

Explanation: An empty array has no non-empty subarray, so the requirement cannot be met.

Input: ([1, 2, 2, 3, 1], 2)

Expected Output: 2

Explanation: A shortest valid subarray is [1, 2] or [2, 3], both with 2 distinct integers and length 2.

Input: ([4, -1, 4, -1, 2], 3)

Expected Output: 3

Explanation: The subarray [4, -1, 2] contains 3 distinct integers and has length 3, which is minimal.

Input: ([7, 8], 0)

Expected Output: 0

Explanation: With k = 0, the empty subarray already satisfies the condition.

Hints

Use a sliding window and keep track of the frequency of each value inside the current window.
Whenever the window has at least `k` distinct values, try shrinking it from the left to make it as short as possible.

Last updated: Apr 22, 2026

Loading coding console...