Count Subarrays Where Max Element Appears at Least K Times

Medium Topics Company Tags

Let maximum be the largest value in the entire array nums. Count the nonempty contiguous subarrays that contain at least k occurrences of that value. Return the total count. Use the maximum of the original array, not a separate maximum for each subarray.

Example 1:

Input: nums = [2,1,2]
k = 2

Output: 1

Explanation: The global maximum is 2. Only the full array contains both occurrences, so exactly one subarray qualifies.

Example 2:

Input: nums = [3,3]
k = 1

Output: 3

Explanation: Both singleton subarrays and the full array contain the global maximum 3 at least once. These are three separate subarrays.

Example 3:

Input: nums = [1,2,1]
k = 2

Output: 0

Explanation: The global maximum is 2 and occurs only once in the entire array. No subarray can contain it twice.

Constraints:

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000
  • 1 <= k <= 100000


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.