Frontend School

Shortest Subarray with Minimum Frequency Constraint

DSA
hard

Shortest Subarray with Minimum Frequency Constraint

Hard
Sliding Window
Hash Map
Arrays

Overview

At Groww, understanding user behavior and transaction patterns is crucial for optimizing our platform and offering tailored financial products. One way to gain insights is by analyzing sequences of user actions or portfolio compositions over time. Identifying compact segments of data that meet specific diversity and frequency criteria can highlight key trends or anomalous activities.

This problem challenges you to find the shortest continuous segment (subarray) within a stream of numerical data that satisfies a complex condition related to both the distinctness and frequency of its elements. This mimics scenarios where we might look for a minimal set of transactions exhibiting a certain level of product diversification, where each product type has been traded a minimum number of times.

What you need to do / Task

You are given an array of integers nums, and two positive integers k and m. Your task is to find the length of the shortest non-empty contiguous subarray of nums such that it contains at least k distinct integers, and each of those k distinct integers appears at least m times within that subarray.

If no such subarray exists, return -1.

Input & output

Input:

  • nums: An array of integers representing the data stream. nums[i] is a positive integer.
  • k: A positive integer representing the minimum number of distinct elements required in the subarray.
  • m: A positive integer representing the minimum frequency each of the k distinct elements must have within the subarray.

Output:

  • A number representing the length of the shortest valid subarray, or -1 if no such subarray exists.

Clarifications

  • The subarray must be contiguous.
  • k and m are always positive integers (>= 1).
  • nums will contain positive integers.
  • If multiple subarrays have the same shortest length, any one of them is acceptable, so just return its length.

Examples

1

Example 1

Input:

nums = [1, 2, 1, 3, 2, 1, 4, 3], k = 2, m = 2

Output:

5

Note:

Consider the subarray [2, 1, 3, 2, 1] (length 5). It contains distinct elements {1, 2, 3}. Within this subarray, '1' appears 2 times, '2' appears 2 times, and '3' appears 1 time. We need at least k=2 distinct elements, each appearing m=2 times. Here, '1' and '2' both appear at least 2 times, satisfying the condition for 2 distinct elements. No shorter subarray satisfies the criteria.

2

Example 2

Input:

nums = [1, 1, 1, 2, 2, 3, 3], k = 3, m = 1

Output:

3

Note:

The subarray [1, 2, 3] (length 3) contains distinct elements {1, 2, 3}. Each of these appears 1 time, which satisfies m=1. Since there are 3 such distinct elements, and k=3, this is a valid subarray. It's the shortest possible.

3

Example 3

Input:

nums = [1, 2, 3, 4, 5], k = 2, m = 2

Output:

-1

Note:

In this array, no element appears more than once. Therefore, it's impossible to find any element that appears m=2 times. Consequently, no subarray can satisfy the condition of having at least k=2 distinct elements, each appearing at least m=2 times.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length
  • 1 <= m <= nums.length
  • The solution should aim for optimal time complexity, typically O(N), where N is nums.length.
  • The solution should aim for optimal space complexity, typically O(D) where D is the number of distinct elements in nums (at most N).

Out of scope

  • Handling non-integer inputs or negative numbers in nums.
  • Input validation for k or m being non-positive.
  • Concurrent access to the nums array.

What interviewers evaluate

  • Correctness of Sliding Window Logic: Ability to correctly apply the sliding window pattern for dynamic subarray analysis.
  • Efficient Data Structure Usage: Effective use of hash maps (or similar structures) to track element frequencies and manage counts of distinct elements meeting specific criteria.
  • Edge Case Handling: Proper handling of scenarios where no valid subarray exists or when k or m values are at their extremes.
  • Time and Space Complexity: Analysis and optimization of the solution to meet the specified constraints.

Loading editor...