FastPrep
Problem · Sliding Window

Get Stable Periods Count (Fungible :)

Learn this problem
● MediumAmazon logoAmazonINTERNNEW GRADOA
See Amazon hiring insights

Problem 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:

  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)

Examples

Example 1

revenues = [1, 2, 1]k = 1return = 3
Example 1 illustration
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 = 10
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

  • 1 ≤ n ≤ 10^5
  • 1 ≤ k ≤ n
  • -10^9 ≤ revenues[i] ≤ 10^9

    • More Amazon problems

    drafts saved locally
    public int getStablePeriodsCount(int[] revenues, int k) {
  // write your code here
}
    revenues[1, 2, 1]
    k1
    expected3
    checking account