Shortest Subarray with at Least K Distinct Values

Question

The question asks the candidate to find the minimum length of a subarray that contains at least 'k' distinct integers from a given array of positive integers. If no such subarray exists, the candidate should return -1.

Codemia · Accepted Answer

To solve the problem of finding the minimum length subarray with at least k distinct integers, we can utilize the sliding window technique combined with a hash map. The sliding window will allow us to expand and contract the range of our subarray dynamically, while the hash map will keep track of the count of distinct integers within the current window.

1. Initialize two pointers, `left` and `right`, both starting at the beginning of the array.
2. Use a hash map to count the occurrences of each integer in the current window.
3. Expand the `right` pointer to include more elements until we have at least k distinct integers.
4. Once we have k distinct integers, check the length of the current window and update the minimum length if it's smaller than the previously recorded minimum.
5. Move the `left` pointer to reduce the size of the window while still maintaining at least k distinct integers.
6. Repeat steps 3-5 until the `right` pointer has traversed the entire array.
7. If a valid subarray is found, return its length; otherwise, return -1.

The time complexity of this approach is O(n), where n is the length of the array. This is because each element is processed at most twice (once by the `right` pointer and once by the `left` pointer). The space complexity is O(k), which is the size of the hash map storing the counts of distinct integers.

```python
from collections import defaultdict

def shortest_subarray_with_k_distinct(arr, k):
    left = 0
    min_length = float('inf')
    count = defaultdict(int)
    distinct_count = 0

for right in range(len(arr)):
        if count[arr[right]] == 0:
            distinct_count += 1
        count[arr[right]] += 1

while distinct_count >= k:
            min_length = min(min_length, right - left + 1)
            count[arr[left]] -= 1
            if count[arr[left]] == 0:
                distinct_count -= 1
            left += 1

return min_length if min_length != float('inf') else -1
```
This code defines a function that implements the described algorithm to find the shortest subarray with at least k distinct integers.

Consider edge cases such as when the array is empty or when k is greater than the number of distinct integers in the array. In these cases, the function should return -1 as it is impossible to find a valid subarray.

Shortest Subarray with at Least K Distinct Values

Squarepoint

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Squarepoint Quantitative Researcher Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string