Count Subarrays Where Max Element Appears at Least K Times solution and explanation
Google
9 more videos on this problem
Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - PythonNeetCodeIO · 14:57 · 22K views
Count Subarrays Where Max Element Appears at Least K Times | 2 Approaches | Leetcode 2962codestorywithMIK · 36:06 · 18K views
2962. Count Subarrays Where Max Element Appears at Least K Times | 2 Pointer | Sliding WindowAryan Mittal · 17:46 · 7K views
2962. Count Subarrays Where Max Element Appears at Least K Times | leetcode daily challenge | DSAShashCode · 15:40 · 4K views
Leetcode 2962 | Count Subarrays Where Max Element Appears At Least K Times | SolutionCoding Grower · 8:10 · 368 views
Leetcode | 2962. Count Subarrays Where Max Element Appears at Least K Times | Medium | Java SolutionDeveloper Docs · 9:06 · 279 views
LeetCode 2962 - Count Subarrays Where Max Element Appears at Least K Times - JavaAlpha-Code · 12:01 · 221 views
Count Subarrays Where Max Element Appears at Least K Times- Leetcode 2962 - PythonTim Huang · 3:40 · 189 views
2962. Count Subarrays Where Max Element Appears at Least K Times | Leetcode Daily - PythonLeetcode Daily · 9:40 · 189 views
Leetcode 2962: Count Subarrays Where Max Element Appears at Least K TimesAlgorithms Casts · 13:30 · 115 views
The problem
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 <= 105
Approach overview
Problem 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.
Approach 1: Sliding Window Technique
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.
def count_subarrays(nums, k):
count = max_count = 0
max_element = -1
j = 0
for i in range(len(nums)):
if nums[i] > max_element:
max_element = nums[i]
max_count = 1
elif nums[i] == max_element:
max_count += 1
while max_count >= k:
count += len(nums) - i
if nums[j] == max_element:
max_count -= 1
j += 1
return count
nums = [1, 3, 2, 3, 3]
k = 2
print(count_subarrays(nums, k)) # Output: 6public class Solution {
public int countSubarrays(int[] nums, int k) {
int count = 0, maxCount = 0, maxElement = -1, j = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] > maxElement) {
maxElement = nums[i];
maxCount = 1;
} else if (nums[i] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += n - i;
if (nums[j] == maxElement) {
maxCount--;
}
j++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3, 2, 3, 3};
int k = 2;
System.out.println(sol.countSubarrays(nums, k)); // Output: 6
}
}#include <vector>
#include <iostream>
using namespace std;
int countSubarrays(vector<int>& nums, int k) {
int count = 0, max_count = 0, max_element = -1, j = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > max_element) {
max_element = nums[i];
max_count = 1;
} else if (nums[i] == max_element) {
max_count++;
}
while (max_count >= k) {
count += nums.size() - i;
if (nums[j] == max_element) {
max_count--;
}
j++;
}
}
return count;
}
int main() {
vector<int> nums = {1, 3, 2, 3, 3};
int k = 2;
cout << countSubarrays(nums, k) << endl; // Output: 6
return 0;
}function countSubarrays(nums, k) {
let count = 0, maxCount = 0, maxElement = -1, j = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > maxElement) {
maxElement = nums[i];
maxCount = 1;
} else if (nums[i] === maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.length - i;
if (nums[j] === maxElement) {
maxCount--;
}
j++;
}
}
return count;
}
let nums = [1, 3, 2, 3, 3];
let k = 2;
console.log(countSubarrays(nums, k)); // Output: 6#include <stdio.h>
int countSubarrays(int* nums, int numsSize, int k) {
int count = 0, max_count = 0, max_element = -1, j = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > max_element) {
max_element = nums[i];
max_count = 1;
} else if (nums[i] == max_element) {
max_count++;
}
while (max_count >= k) {
count += numsSize - i;
if (nums[j] == max_element) {
max_count--;
}
j++;
}
}
return count;
}
int main() {
int nums[] = {1, 3, 2, 3, 3};
int k = 2;
printf("%d\n", countSubarrays(nums, 5, k)); // Output: 6
return 0;
}using System;
public class Solution {
public int CountSubarrays(int[] nums, int k) {
int count = 0, maxCount = 0, maxElement = -1, j = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
if (nums[i] > maxElement) {
maxElement = nums[i];
maxCount = 1;
} else if (nums[i] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += n - i;
if (nums[j] == maxElement) {
maxCount--;
}
j++;
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3, 2, 3, 3};
int k = 2;
Console.WriteLine(sol.CountSubarrays(nums, k)); // Output: 6
}
}This Python function uses a sliding window approach to efficiently determine when the current subarray meets the required condition of containing the maximum element at least k times. The two pointers (i and j) allow us to maintain and update the window as needed.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), constant space is used.
Approach 2: Two-Pointer Approach with Reset
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.
def count_subarrays(nums, k):
count = 0
left = 0
max_element = 0
max_count = 0
for right in range(len(nums)):
if nums[right] > max_element:
max_element = nums[right]
max_count = 1
elif nums[right] == max_element:
max_count += 1
while max_count >= k:
count += len(nums) - right
if nums[left] == max_element:
max_count -= 1
left += 1
return count
nums = [1, 3, 2, 3, 3]
k = 2
print(count_subarrays(nums, k)) # Output: 6public class Solution {
public int countSubarrays(int[] nums, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.length - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3, 2, 3, 3};
int k = 2;
System.out.println(sol.countSubarrays(nums, k)); // Output: 6
}
}#include <vector>
#include <iostream>
using namespace std;
int countSubarrays(vector<int>& nums, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < nums.size(); right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.size() - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
int main() {
vector<int> nums = {1, 3, 2, 3, 3};
int k = 2;
cout << countSubarrays(nums, k) << endl; // Output: 6
return 0;
}function countSubarrays(nums, k) {
let count = 0, left = 0, maxElement = 0, maxCount = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] === maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.length - right;
if (nums[left++] === maxElement) {
maxCount--;
}
}
}
return count;
}
let nums = [1, 3, 2, 3, 3];
let k = 2;
console.log(countSubarrays(nums, k)); // Output: 6#include <stdio.h>
int countSubarrays(int* nums, int numsSize, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < numsSize; right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += numsSize - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
int main() {
int nums[] = {1, 3, 2, 3, 3};
int k = 2;
printf("%d\n", countSubarrays(nums, 5, k)); // Output: 6
return 0;
}using System;
public class Solution {
public int CountSubarrays(int[] nums, int k) {
int count = 0, left = 0, maxElement = 0, maxCount = 0;
for (int right = 0; right < nums.Length; right++) {
if (nums[right] > maxElement) {
maxElement = nums[right];
maxCount = 1;
} else if (nums[right] == maxElement) {
maxCount++;
}
while (maxCount >= k) {
count += nums.Length - right;
if (nums[left++] == maxElement) {
maxCount--;
}
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3, 2, 3, 3};
int k = 2;
Console.WriteLine(sol.CountSubarrays(nums, k)); // Output: 6
}
}This Python function maintains a two-point tracking mechanism for efficiently checking valid subsequences while managing dynamic changes in maximum element count.
Time Complexity: O(n), one full traversal of nums.
Space Complexity: O(1), constant space via variables and pointers only.
Approach 3: Two Pointers
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).
function countSubarrays(nums: number[], k: number): number {
const mx = Math.max(...nums);
const n = nums.length;
let [cnt, j] = [0, 0];
let ans = 0;
for (const x of nums) {
for (; j < n && cnt < k; ++j) {
cnt += nums[j] === mx ? 1 : 0;
}
if (cnt < k) {
break;
}
ans += n - j + 1;
cnt -= x === mx ? 1 : 0;
}
return ans;
}func countSubarrays(nums []int, k int) (ans int64) {
mx := slices.Max(nums)
n := len(nums)
cnt, j := 0, 0
for _, x := range nums {
for ; j < n && cnt < k; j++ {
if nums[j] == mx {
cnt++
}
}
if cnt < k {
break
}
ans += int64(n - j + 1)
if x == mx {
cnt--
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), where n is the length of nums. |
| Two-Pointer Approach with Reset | Time Complexity: O(n), one full traversal of nums. |
| Two Pointers | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Subarrays Where Max Element Appears at Least K Times easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing that only the global maximum matters and translating the "at least k occurrences" condition into a sliding window counting strategy.
Count Subarrays Where Max Element Appears at Least K Times Python/Java solution
In Python or Java, the solution uses two pointers and a counter tracking how many times the maximum element appears in the current window. Each time the count reaches k, move the left pointer while updating the count and accumulate the number of valid starting positions. The algorithm runs in O(n) time and constant space.
How to solve Count Subarrays Where Max Element Appears at Least K Times in O(n)?
Find the global maximum value in the array. Use a sliding window with two pointers and track how many times the maximum appears inside the window. When the count reaches k, move the left pointer until the count drops below k and add the current left index to the result for each right pointer position. This counts all valid subarrays ending at that position in linear time.
What is the best approach for Count Subarrays Where Max Element Appears at Least K Times?
The sliding window approach is the most efficient solution. First compute the global maximum of the array, then expand a window with a right pointer while tracking how many times the maximum appears. When the count reaches k, shrink the window from the left and count valid subarrays. This runs in O(n) time with O(1) extra space.
Is Count Subarrays Where Max Element Appears at Least K Times asked at Google/Amazon/Meta?
Problems involving sliding window subarray counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to maintain frequency constraints inside a dynamic window and compute counts efficiently.
What data structure is used in Count Subarrays Where Max Element Appears at Least K Times?
The optimal implementation mainly uses the sliding window pattern with two pointers and simple counters. Some variants also maintain a queue or list of indices where the maximum element appears to help count valid subarrays.
What is the time complexity of Count Subarrays Where Max Element Appears at Least K Times?
The optimal solution runs in O(n) time because each element is processed at most twice by the sliding window pointers. Space complexity is O(1) since only counters and pointer variables are maintained. A naive brute-force approach would take O(n^2) by checking every subarray.