Frontend School

Shortest Trending Product Bundle

DSA
medium

Shortest Trending Product Bundle

Medium
Two Pointers
Sliding Window
Hash Map

Overview

At Nykaa, understanding product trends is crucial for merchandising, inventory management, and promotional strategies. One way to identify emerging trends is by analyzing 'product bundles' – contiguous sequences of products. We're interested in finding the most compact bundles that feature a diverse range of categories.

Your task is to identify the shortest possible contiguous product bundle (subarray) from a given list of category IDs that contains at least k distinct product categories. This helps us quickly pinpoint compact, high-diversity product groupings.

What you need to do / Task

Implement the function findShortestBundle that takes an array of product category IDs (categories) and an integer k.

Your function should return the length of the shortest contiguous subarray (bundle) within categories that contains at least k distinct category IDs. If no such bundle exists, return -1.

Input & output

  • Input:
    • categories: An array of numbers, where each number represents a unique product category ID. categories[i] is the category ID of the i-th product.
    • k: A number representing the minimum required count of distinct product categories in the bundle.
  • Output: A number representing the length of the shortest valid bundle. Return -1 if no such bundle can be found.

Clarifications

  • An empty input array categories cannot form any bundle, so for any k >= 1, the result should be -1.
  • Category IDs can be non-negative integers and may be large, implying the use of a data structure that handles arbitrary values, not just array indices.
  • If k is greater than the total number of unique categories present in the entire categories array, it's impossible to form such a bundle, and -1 should be returned.

Examples

1

Example 1

Input:

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

Output:

3

Note:

The bundle [2, 1, 3] (indices 1-3) contains distinct categories {1, 2, 3}, which is 3 distinct categories. Its length is 3. Another valid bundle is [1, 3, 2] (indices 2-4), also length 3. This is the shortest possible length.

2

Example 2

Input:

categories = [1, 1, 1, 1, 1], k = 2

Output:

-1

Note:

The array only contains one distinct category (1). It's impossible to form a bundle with 2 distinct categories.

3

Example 3

Input:

categories = [5, 6, 7, 8, 9], k = 5

Output:

5

Note:

The entire array [5, 6, 7, 8, 9] forms a bundle with 5 distinct categories. Its length is 5, which is the shortest possible.

4

Example 4

Input:

categories = [], k = 1

Output:

-1

Note:

The input array is empty, so no bundle can be formed.

Constraints

Constraints & assumptions

  • 1 <= categories.length <= 10^5
  • 0 <= categories[i] <= 10^9
  • 1 <= k <= categories.length
  • The solution should aim for optimal time complexity, typically O(N) where N is the length of categories.
  • Space complexity should be reasonable, ideally O(U) where U is the number of unique categories in the input array.

What interviewers evaluate

  • Correct application of the Two Pointers / Sliding Window technique.
  • Efficient use of auxiliary data structures (e.g., hash map) to track distinct element counts.
  • Robust handling of edge cases, including empty input, k being unreachable, or k being 1.
  • Clarity, readability, and maintainability of the code.

Loading editor...