Shortest Subarray with Minimum Frequency Constraint
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.
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:
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:
number representing the length of the shortest valid subarray, or -1 if no such subarray exists.k and m are always positive integers (>= 1).nums will contain positive integers.Examples
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.
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.
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
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= k <= nums.length1 <= m <= nums.lengthnums.length.nums (at most N).nums.k or m being non-positive.nums array.k or m values are at their extremes.Loading editor...