Frontend School

Minimum Subarray with K Distinct Categories

DSA
medium

Minimum Subarray with K Distinct Categories

Medium
Arrays
Hashing
Sliding Window

Overview

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.

What you need to do / Task

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 & output

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:

  • An integer (number) representing the minimum length of a contiguous subarray that satisfies the condition. Return -1 if no such subarray exists.

Clarifications

  • Empty 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.
  • Duplicate categories: Categories with the same ID are considered the same distinct category. For example, [1, 2, 1] has 2 distinct categories (1 and 2).

Examples

1

Example 1

Input:

categoryIds = [1, 2, 1, 3, 2, 4], k = 3

Output:

3

Note:

Subarrays with at least 3 distinct categories:

  • [1, 2, 1, 3] has {1,2,3}, length 4.
  • [2, 1, 3] has {1,2,3}, length 3.
  • [1, 3, 2] has {1,2,3}, length 3.
  • [3, 2, 4] has {2,3,4}, length 3. The minimum length among these is 3.
2

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.

3

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

Constraints & assumptions

  • 1 <= categoryIds.length <= 10^5
  • 1 <= categoryIds[i] <= 10^9 (Category IDs can be large, but their count matters, not their value).
  • 1 <= k <= categoryIds.length
  • The input categoryIds will only contain positive integers.

Out of scope

  • Handling invalid input types (e.g., categoryIds not an array, k not an integer). Assume valid inputs as per constraints.
  • Optimizations for distributed systems or extremely large datasets beyond memory limits.
  • Modifying the input categoryIds array.

What interviewers evaluate

  • Correctness: The solution must accurately identify the minimum length subarray for all valid inputs, including edge cases.
  • Efficiency: The solution should demonstrate optimal time and space complexity, ideally using a sliding window approach with hashing.
  • Code Structure & Readability: Clean, well-organized code with meaningful variable names and appropriate comments where necessary.
  • Edge Case Handling: Proper handling of scenarios like k being larger than available distinct categories, or arrays where no solution is possible.

Loading editor...