For an array of n positive integers arr[n] 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.
findMinimumLengthSubarray has the following parameter(s):
- int arr[n]: the array to partition
- int k: the number of distinct elements a good subarray must contain
Returns
- int: the minimum length possible for a good subarray, or -1 if there is none
This problem requires finding the smallest contiguous subarray that contains at least k distinct integers. A natural way to approach it is using the sliding window technique: expand the right pointer to include new elements and track distinct counts, then shrink the left pointer while maintaining at least k distinct values to minimize the window length. If no window satisfies the condition, return -1.
