Katkat
Back

Find shortest subarray with ≥k distinct integers

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to solve subarray problems using the sliding window (two-pointer) technique and hash maps to track element frequencies.

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

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] or [2, 1], both 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

  • If k is greater than the total number of unique elements in the entire array, return 0.
  • If the array contains all identical elements and k > 1, return 0.
  • Arrays with a single element where k=1 should return 1.

Hints

Hint 1

Use a sliding window approach with two pointers, 'left' and 'right', to represent the current subarray.

Hint 2

Maintain a hash map or frequency array to keep track of the count of each integer within the current window and a variable to track the number of distinct elements.

Hint 3

Whenever the number of distinct elements in the window is at least 'k', attempt to shrink the window from the left to minimize its length while still maintaining at least 'k' distinct elements.

Follow-up questions

  • How would your solution change if you needed to return the start and end indices of the shortest subarray instead of just the length?
  • What is the time complexity of your solution, and can you explain how the hash map operations affect the overall performance?
  • If the array was sorted, would there be a more efficient way to solve this than the sliding window approach?