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 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.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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`

Quick Answer: 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.

Given an integer array `nums` and an integer `k`, find the length of the **shortest contiguous subarray** that contains **at least `k` distinct integers**. Return the minimum length of such a subarray. If no subarray contains at least `k` distinct integers, return `-1`. ### Examples - `nums = [1,2,1,3,4], k = 3` → `3` (e.g., the subarray `[2,1,3]` has 3 distinct values) - `nums = [1,1,1], k = 2` → `-1` (only 1 distinct value exists overall) ### Approach Use a sliding window with a frequency hash map. Expand the window's right edge, and whenever the window holds at least `k` distinct integers, shrink it from the left as far as possible while still satisfying the constraint, recording the minimum length. Each element is added and removed at most once, giving O(n) time.

Constraints

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

Examples

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

Expected Output: 3

Explanation: The subarray [2,1,3] (indices 1..3) has 3 distinct values, and no shorter contiguous subarray reaches 3 distinct.

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

Expected Output: -1

Explanation: The array contains only the value 1, so no subarray can ever have 2 distinct integers.

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

Expected Output: 5

Explanation: All values are unique; the only window with 5 distinct values is the whole array of length 5.

Input: ([5], 1)

Expected Output: 1

Explanation: A single element already has 1 distinct value, so the minimum length is 1.

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

Expected Output: 1

Explanation: k=1 is satisfied by any single element, giving a minimum length of 1 even though all values are identical.

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

Expected Output: 4

Explanation: The window [2,3,1,4] (indices 2..5) holds all 4 distinct values 1,2,3,4 with length 4; no shorter window covers 4 distinct.

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

Expected Output: 3

Explanation: Negative values are handled the same way; [-1,-2,-3] (indices 0..2) gives 3 distinct values in length 3.

Input: ([7,7,8,7,9,7], 3)

Expected Output: 3

Explanation: Distinct values are 7,8,9; the window [8,7,9] (indices 2..4) reaches all 3 distinct in length 3.

Hints

A brute-force scan over all subarrays is O(n^2) or worse. Can you avoid recomputing distinct counts from scratch?
Maintain a sliding window [left, right] and a frequency map. Track how many distinct values are currently inside the window.
Whenever the window contains at least k distinct integers, it is valid — record its length, then shrink from the left to find the smallest valid window ending at the current right.
Each element enters and leaves the window at most once, so the two pointers move a total of O(n) times.

Quick Overview

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.