Get Stable Periods Count (Fungible :)
Amazon● MediumINTERNNEW GRADOAProblem statement
A team of financial analysts at Amazon closely monitors revenue generated by a newly launched product. They classify a period of one or more consecutive days as a stable-growth period if the revenue generated by the product takes no more than k distinct values over that period.
Given an array revenues of size n, that represents the revenues generated by the new product on n consecutive days, and an integer k, determine the total number of stable growth periods over the n days. Since the answer can be large, return it modulo (10^9 + 7).
Function
getStablePeriodsCount(revenues: int[], k: int) → int
Complete the function getStablePeriodsCount in the editor.
getStablePeriodsCount has the following parameters:
int revenues[n]: the revenues generated by the new product overndaysint k: the maximum number of distinct values in a stable growth period
Returns
int: the number of stable growth periods of the product over n days, modulo (10^9 + 7)
Examples
Example 1
revenues = [1, 2, 1]k = 1return = 3
There are 3 periods with k=1 or fewer distinct values. The number of stable growth periods is 3.
Example 2
revenues = [2, -3, 2, -3]k = 2return = 10Any contiguous period of 1 or more days has 2 or fewer distinct values, thus all 10 subarrays represent a period of stable growth 📈📈
Constraints
- 1 ≤
n≤ 10^5 - 1 ≤
k≤n - -10^9 ≤
revenues[i]≤ 10^9