Minimum Subarray with K Distinct Categories
Livspace manages a vast inventory of home decor and furniture items, categorized to ensure efficient organization and customer browsing. Imagine optimizing the display of products on a digital shelf or in a physical showroom. To maintain visual appeal and ensure diverse representation, it's crucial to avoid long stretches dominated by too few product categories. This problem challenges you to find the most compact segment of products that still offers a good variety of categories.
You are given an array of integers categoryIds, where each integer represents the ID of a product category. You are also given an integer k. Your task is to find the minimum length of a contiguous subarray within categoryIds that contains at least k distinct product categories.
If no such subarray exists (i.e., it's impossible to find a subarray with at least k distinct categories), you should return -1.
Input:
categoryIds: An array of integers (number[]), where each integer categoryIds[i] represents the category ID of the i-th product.k: An integer (number) representing the minimum number of distinct categories required in the subarray.Output:
number) representing the minimum length of a contiguous subarray that satisfies the condition. Return -1 if no such subarray exists.categoryIds: If categoryIds is empty and k > 0, the answer should be -1. (Note: Constraints specify categoryIds.length >= 1).k larger than total distinct categories: If k is greater than the total number of distinct categories available in the entire categoryIds array, then it's impossible to satisfy the condition, and the answer should be -1.[1, 2, 1] has 2 distinct categories (1 and 2).Examples
Example 1
Input:
categoryIds = [1, 2, 1, 3, 2, 4], k = 3
Output:
3
Note:
Subarrays with at least 3 distinct categories:
Example 2
Input:
categoryIds = [1, 1, 1, 1], k = 2
Output:
-1
Note:
The array only contains one distinct category (1). It's impossible to find a subarray with at least 2 distinct categories.
Example 3
Input:
categoryIds = [5, 4, 3, 2, 1], k = 5
Output:
5
Note:
The entire array [5, 4, 3, 2, 1] is the shortest subarray containing 5 distinct categories {1,2,3,4,5}. Its length is 5.
Constraints
1 <= categoryIds.length <= 10^51 <= categoryIds[i] <= 10^9 (Category IDs can be large, but their count matters, not their value).1 <= k <= categoryIds.lengthcategoryIds will only contain positive integers.categoryIds not an array, k not an integer). Assume valid inputs as per constraints.categoryIds array.k being larger than available distinct categories, or arrays where no solution is possible.Loading editor...