Count Subarrays with at Least k Occurrences of the Global Maximum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Subarrays with at Least k Occurrences of the Global Maximum
You are given an integer array `nums` and a positive integer `k`. Let `M` be the maximum value in the entire input array.
Return the number of contiguous subarrays in which `M` occurs at least `k` times. The maximum is fixed from the whole input, rather than recomputed separately for each subarray.
### Examples
**Example 1**
```text
Input: nums = [4,1,4,2,4], k = 2
Output: 5
```
The global maximum is `4`. The five qualifying index intervals are `(0,2)`, `(0,3)`, `(0,4)`, `(1,4)`, and `(2,4)`. The full array contains three occurrences of `4` and qualifies because the requirement is at least two.
**Example 2**
```text
Input: nums = [2,9,2], k = 4
Output: 0
```
The global maximum `9` occurs only once in the whole array, so no subarray can contain it four times. The source bounds allow `k` to exceed the array length.
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^6`.
- `1 <= k <= 10^5`.
### Clarifying Questions
- Does a subarray containing a smaller local maximum qualify on that basis? No; only occurrences of the global maximum `M` matter.
- Must `M` occur exactly `k` times? No; any count at least `k` qualifies.
- Are intervals with identical values at different positions counted separately? Yes; each index interval is a different subarray.
- Can `k` exceed the array length or the total frequency of `M`? Yes; then the answer is zero.
- Do empty intervals contribute? No; since `k` is positive, an empty interval cannot contain the required occurrences anyway.
### C++ Interface
```cpp
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
}
};
```
### Reasoning Checkpoints
- Use the input-wide maximum consistently and preserve the at-least condition.
- Count each qualifying interval once without merging equal-value intervals.
- Handle large counts and thresholds greater than the available occurrences.
```hint Count valid starts for each right endpoint
Track the number of global-maximum occurrences in a moving interval. Move its left endpoint until the remaining interval has fewer than k. Which earlier starts still give qualifying subarrays ending at the current right endpoint?
```
Overview: Count contiguous subarrays containing at least k occurrences of the maximum value from the entire input array, including intervals with more than k occurrences.
