You are given an integer array nums and a positive integer k.
Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,3,2,3,3], k = 2 Output: 6 Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
Example 2:
Input: nums = [1,4,2,1], k = 3 Output: 0 Explanation: No subarray contains the element 4 at least 3 times.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= k <= 105Problem Overview: Given an integer array nums, count how many subarrays contain the maximum element of the entire array at least k times. The key observation: only the global maximum matters. Any valid subarray must include that value at least k times.
Approach 1: Sliding Window Technique (O(n) time, O(1) space)
First compute the global maximum of the array. Use a classic sliding window with two pointers left and right. Expand right across the array and count how many times the maximum appears inside the window. Whenever the count reaches k, start shrinking the window from the left until the count drops below k. For every position of right, the number of valid subarrays ending at right equals the current left pointer value. This works because any starting index before left still keeps at least k maximum elements in the window. The algorithm scans the array once, giving O(n) time and O(1) extra space.
Approach 2: Two-Pointer Approach with Max Index Tracking (O(n) time, O(k) space)
Another view is to track the indices where the global maximum appears. As you iterate through the array, push each max index into a list or queue. Once you have at least k occurrences, the earliest valid start of a subarray that includes those k maxima is the index of the (count-k)th maximum plus one. Every extension of the right pointer forms additional valid subarrays starting from earlier positions. This effectively behaves like a two-pointer scan but driven by the positions of the maximum values. Time complexity remains O(n), while space is O(k) for storing recent max indices.
Recommended for interviews: The sliding window approach is what interviewers expect for problems involving subarray counts with frequency constraints. It shows you recognize a variable-size window pattern and can translate a frequency condition into pointer movement. A brute-force enumeration would be O(n^2) or worse and mainly demonstrates baseline understanding, while the sliding window demonstrates real algorithmic skill with array traversal.
This approach utilizes the sliding window technique to efficiently count subarrays that satisfy the given condition. By maintaining a window and a count of the occurrences of the maximum element within that window, we can determine the valid subarrays as we expand and contract the window.
The code initializes a sliding window by setting pointers i and j. As we iterate through the array, we update the current maximum element and its count within the window. When the count of the maximum element reaches k or more, we add subarrays from the start of the window to the end of the array that satisfy the condition.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), only constant space is used for variables.
This strategy involves iterating through the array with two pointers, resetting conditions when new maximum elements are encountered and calculating valid subarrays based on maximum occurrence counts.
The C code uses two pointers (left and right) to validate subarrays. When a maximum condition changes, the calculation restarts, which ensures only subarrays with the required maximum occurrence are considered.
Time Complexity: O(n), as we process each element in nums.
Space Complexity: O(1), no extra space besides pointer variables.
Let's denote the maximum value in the array as mx.
We use two pointers i and j to maintain a sliding window, such that in the subarray between [i, j), there are k elements equal to mx. If we fix the left endpoint i, then all right endpoints greater than or equal to j-1 meet the condition, totaling n - (j - 1).
Therefore, we enumerate the left endpoint i, use the pointer j to maintain the right endpoint, use a variable cnt to record the number of elements equal to mx in the current window. When cnt is greater than or equal to k, we have found a subarray that meets the condition, and we increase the answer by n - (j - 1). Then we update cnt and continue to enumerate the next left endpoint.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), where n is the number of elements in nums. |
| Two-Pointer Approach with Reset | Time Complexity: O(n), as we process each element in nums. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^2) | O(1) | Conceptual baseline or small input sizes |
| Sliding Window Technique | O(n) | O(1) | Best general solution for counting subarrays with frequency constraints |
| Two-Pointer with Max Index Tracking | O(n) | O(k) | Useful when tracking positions of important values simplifies counting logic |
Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - Python • NeetCodeIO • 22,296 views views
Watch 9 more video solutions →Practice Count Subarrays Where Max Element Appears at Least K Times with our built-in code editor and test cases.
Practice on FleetCode