FastPrepFastPrep
Problem Brief

Get Stable Periods Count (Fungible :)

INTERNNEW GRADOA
See Amazon online assessment and hiring insights

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 Description

Complete the function getStablePeriodsCount in the editor.

getStablePeriodsCount has the following parameters:

  1. int revenues[n]: the revenues generated by the new product over n days
  2. int 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)

1Example 1

Input
revenues = [1, 2, 1], k = 1
Output
3
Explanation
Example 1 illustration
There are 3 periods with k=1 or fewer distinct values. The number of stable growth periods is 3.

2Example 2

Input
revenues = [2, -3, 2, -3], k = 2
Output
10
Explanation
Any contiguous period of 1 or more days has 2 or fewer distinct values, thus all 10 subarrays represent a period of stable growth 📈📈

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10^5
  • 1 ≤ k ≤ n
  • -10^9 ≤ revenues[i] ≤ 10^9
    • public int getStablePeriodsCount(int[] revenues, int k) {
  // write your code here
}
    Input

    revenues

    [1, 2, 1]

    k

    1

    Output

    3

    Sign in to submit your solution.