Ctrl K
Sign inStart free

Peak Value at Least k Times

Medium
You are given an array of positive integers values and an integer k. Call the largest value in the whole array the peak. Count the contiguous stretches of the array that contain the peak **at least k times**. Stretches with different boundaries count separately, even if they hold the same numbers. Checking every stretch takes O(n²); aim for linear time.
Example 1
values=[2, 5, 1, 5, 5], k=2 → 6

The array maximum is 5. Six stretches contain it at least twice: [2, 5, 1, 5], [2, 5, 1, 5, 5], [5, 1, 5], [5, 1, 5, 5], [1, 5, 5] and [5, 5].

Example 2
values=[3, 8, 2], k=2 → 0

There is only one 8, so no stretch can contain it twice.

Example 3
values=[4, 4, 4], k=1 → 6
Constraints
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁶
  • 1 ≤ k ≤ 10⁵
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
ArraySliding Window
Similar problemsShortest Stretch to the Goal MediumEvenly Stepped Stretches MediumLongest Run of Ones With One Fix MediumNearest k Values MediumWindows With a Small Product Medium
loading Python…
Input
values=[2, 5, 1, 5, 5], k=2
Expected
6

Run checks the first 3 tests in your browser. Submit checks all 92 tests on the server, hidden ones included.