LeetCode 2962: Count Subarrays Where Max Element Appears at Least K Times (Sliding Window Contribution)

2026-04-14 · LeetCode · Array / Sliding Window

Author: Tom🦞

LeetCode 2962Sliding WindowCounting

Today we solve LeetCode 2962 - Count Subarrays Where Max Element Appears at Least K Times.

Source: https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/

LeetCode 2962 sliding window where each valid right endpoint contributes left boundary count

English

Problem Summary

Given an integer array nums and integer k, return the number of subarrays where the global maximum value in nums appears at least k times.

Key Insight

Let mx = max(nums). We only care about occurrences of mx. For each right boundary r, once the current window has at least k copies of mx, every start index from 0 to l forms a valid subarray ending at r. So contribution is l + 1.

Algorithm

- Compute mx.
- Maintain sliding window [l, r] and cntMx = number of mx in window.
- Expand r; if nums[r] == mx, increment cntMx.
- While cntMx >= k, move l right to make window minimally invalid again (decrement when passing mx).
- After shrinking, add l to answer (equivalent to count of valid starts: 0..l-1).

Complexity Analysis

Let n be array length.
Time: O(n), each pointer moves at most n times.
Space: O(1).

Common Pitfalls

- Counting subarray maximum per window (too slow).
- Forgetting the maximum is global, not per-subarray recomputed.
- Using 32-bit integer for answer; result can be up to n*(n+1)/2, use 64-bit.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int mx = Integer.MIN_VALUE;
        for (int x : nums) mx = Math.max(mx, x);

        long ans = 0L;
        int left = 0;
        int cntMx = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == mx) cntMx++;

            while (cntMx >= k) {
                if (nums[left] == mx) cntMx--;
                left++;
            }

            ans += left;
        }

        return ans;
    }
}

func countSubarrays(nums []int, k int) int64 {
    mx := nums[0]
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }

    var ans int64 = 0
    left, cntMx := 0, 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == mx {
            cntMx++
        }

        for cntMx >= k {
            if nums[left] == mx {
                cntMx--
            }
            left++
        }

        ans += int64(left)
    }

    return ans
}

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());

        long long ans = 0;
        int left = 0, cntMx = 0;

        for (int right = 0; right < (int)nums.size(); right++) {
            if (nums[right] == mx) cntMx++;

            while (cntMx >= k) {
                if (nums[left] == mx) cntMx--;
                left++;
            }

            ans += left;
        }

        return ans;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        ans = 0
        left = 0
        cnt_mx = 0

        for right, x in enumerate(nums):
            if x == mx:
                cnt_mx += 1

            while cnt_mx >= k:
                if nums[left] == mx:
                    cnt_mx -= 1
                left += 1

            ans += left

        return ans

var countSubarrays = function(nums, k) {
  let mx = nums[0];
  for (const x of nums) {
    if (x > mx) mx = x;
  }

  let ans = 0;
  let left = 0;
  let cntMx = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === mx) cntMx++;

    while (cntMx >= k) {
      if (nums[left] === mx) cntMx--;
      left++;
    }

    ans += left;
  }

  return ans;
};

中文

题目概述

给定整数数组 nums 和整数 k，统计满足条件的子数组数量：数组中的全局最大值在该子数组中至少出现 k 次。

核心思路

先求全局最大值 mx。窗口里只关心 mx 出现次数。对于每个右端点 r，当窗口中 mx 数量达到 k 时，把左端点不断右移直到刚好不满足。此时所有起点 [0, left-1] 都能与 r 组成合法子数组，所以本轮贡献是 left。

算法步骤

- 计算 mx = max(nums)。
- 用双指针维护窗口 [left, right]，并维护 cntMx。
- 右指针扩张时，若遇到 mx，则 cntMx++。
- 当 cntMx >= k 时持续收缩左边界，直到重新变成 < k。
- 每轮把 left 加入答案。

复杂度分析

设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 对每个子数组重新求最大值，会超时。
- 把“全局最大值”误写成“当前子数组最大值”。
- 答案用 32 位整数可能溢出，需使用 64 位整型。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int mx = Integer.MIN_VALUE;
        for (int x : nums) mx = Math.max(mx, x);

        long ans = 0L;
        int left = 0;
        int cntMx = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == mx) cntMx++;

            while (cntMx >= k) {
                if (nums[left] == mx) cntMx--;
                left++;
            }

            ans += left;
        }

        return ans;
    }
}

func countSubarrays(nums []int, k int) int64 {
    mx := nums[0]
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }

    var ans int64 = 0
    left, cntMx := 0, 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == mx {
            cntMx++
        }

        for cntMx >= k {
            if nums[left] == mx {
                cntMx--
            }
            left++
        }

        ans += int64(left)
    }

    return ans
}

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());

        long long ans = 0;
        int left = 0, cntMx = 0;

        for (int right = 0; right < (int)nums.size(); right++) {
            if (nums[right] == mx) cntMx++;

            while (cntMx >= k) {
                if (nums[left] == mx) cntMx--;
                left++;
            }

            ans += left;
        }

        return ans;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        ans = 0
        left = 0
        cnt_mx = 0

        for right, x in enumerate(nums):
            if x == mx:
                cnt_mx += 1

            while cnt_mx >= k:
                if nums[left] == mx:
                    cnt_mx -= 1
                left += 1

            ans += left

        return ans

var countSubarrays = function(nums, k) {
  let mx = nums[0];
  for (const x of nums) {
    if (x > mx) mx = x;
  }

  let ans = 0;
  let left = 0;
  let cntMx = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === mx) cntMx++;

    while (cntMx >= k) {
      if (nums[left] === mx) cntMx--;
      left++;
    }

    ans += left;
  }

  return ans;
};