Microsoft OA Interview Question: Minimum Length Subarray with at Least K Distinct Integers

For an array of n positive integers arr and an integer k, a subarray is considered good if it consists of at least k distinct integers. Find the minimum length subarray that is good. If there is no such subarray, return -1.

Example

arr = [2, 2, 1, 1, 3]
k = 3

The subarrays with at least k = 3 distinct integers are [2, 2, 1, 1, 3] and [2, 1, 1, 3]. Return 4, the minimum length of a good subarray.

Function Description

Complete the function findMinimumLengthSubarray in the editor below.

• INTEGER_ARRAY arr: the array to partition
• INTEGER k: the number of distinct elements a good subarray must contain

The function is expected to return an INTEGER.

This problem asks for the shortest contiguous subarray that contains at least k distinct integers. The standard solution uses a sliding window with a hash map to track element frequencies. Expand the right boundary until the window has enough distinct values, then shrink from the left as much as possible while preserving the condition, updating the minimum length along the way. If no valid window exists, return -1. The key idea is a two-pointer window with frequency counting, which runs in O(n) time.