Katkat
Back

Find shortest subarray with at least k distinct

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window (two-pointer) technique combined with hash maps to find an optimal subarray satisfying a frequency constraint.

Problem Statement

Given an array of integers nums and an integer k, find the length of the shortest contiguous subarray that contains at least k distinct integers. If no such subarray exists, return -1.

Function Signature

def shortest_subarray_with_k_distinct(nums: List[int], k: int) -> int:

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

Examples

Example 1: Input: nums = [1, 2, 1, 2, 3], k = 2 Output: 2 Explanation: The shortest subarrays with at least 2 distinct integers are [1, 2], [2, 1], and [1, 2], all of length 2.

Example 2: Input: nums = [1, 2, 1, 3], k = 3 Output: 3 Explanation: The shortest subarray with at least 3 distinct integers is [2, 1, 3].

Edge Cases

  • What if k is larger than the number of unique elements in the entire array?
  • What if the array contains only one unique element?

Hints

Hint 1

Consider using a sliding window approach with two pointers, `left` and `right`, to maintain a dynamic range of the array.

Hint 2

Use a hash map (or frequency dictionary) to keep track of the count of each integer currently inside the window to determine when you have exactly `k` distinct elements.

Hint 3

Once you have `k` distinct elements in the window, shrink the window from the `left` as much as possible while maintaining at least `k` distinct elements to update your minimum length.

Follow-up questions

  • How would you modify your solution if you needed to return the start and end indices of the shortest subarray rather than just its length?
  • If the array were sorted, could you achieve the same result with better space complexity?
  • What is the time complexity of your solution, and can you explain how the number of distinct elements affects the performance?