Skip to content

2962. Count Subarrays Where Max Element Appears at Least K Times 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long countSubarrays(vector<int>& nums, int k) {
    const int maxNum = ranges::max(nums);
    long ans = 0;
    int count = 0;

    for (int l = 0, r = 0; r < nums.size(); ++r) {
      if (nums[r] == maxNum)
        ++count;
      // Keep the window to include k - 1 times of the maximum number.
      while (count == k)
        if (nums[l++] == maxNum)
          --count;
      // If l > 0, nums[l..r] has k - 1 times of the maximum number. For any
      // subarray nums[i..r], where i < l, it will have at least k times of the
      // maximum number, since nums[l - 1] equals the maximum number.
      ans += l;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public long countSubarrays(int[] nums, int k) {
    final int maxNum = Arrays.stream(nums).max().getAsInt();
    long ans = 0;
    int count = 0;

    for (int l = 0, r = 0; r < nums.length; ++r) {
      if (nums[r] == maxNum)
        ++count;
      // Keep the window to include k - 1 times of the maximum number.
      while (count == k)
        if (nums[l++] == maxNum)
          --count;
      // If l > 0, nums[l..r] has k - 1 times of the maximum number. For any
      // subarray nums[i..r], where i < l, it will have at least k times of the
      // maximum number, since nums[l - 1] equals the maximum number.
      ans += l;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def countSubarrays(self, nums: list[int], k: int) -> int:
    maxNum = max(nums)
    ans = 0
    count = 0

    l = 0
    for r, num in enumerate(nums):
      if num == maxNum:
        count += 1
      # Keep the window to include k - 1 times of the maxNummum number.
      while count == k:
        if nums[l] == maxNum:
          count -= 1
        l += 1
      # If l > 0, nums[l:r+1] has k - 1 times of the maxNummum number. For any
      # subarray nums[i:r+1], where i < l, it will have at least k times of the
      # maxNummum number, since nums[l - 1] equals the maxNummum number.
      ans += l

    return ans