Count Subarrays Where Max Element Appears at Least K Times Solution
Count Subarrays Where Max Element Appears at Least K Times solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Subarrays Where Max Element Appears at Least K Times is a medium coding problem on arrays and sliding window, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sliding Window
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and a positive integer k.
Let M be the maximum element of the whole array. Return the number of non-empty contiguous subarrays in which M appears at least k times.
CodeKairo note: the original allows nums.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.
Example 1
Input: nums = [4,1,4,2,4,3], k = 2
Output: 8
Explanation: The maximum 4 sits at indices 0, 2 and 4. Four subarrays start at index 0 and reach index 2 or beyond; four more start at index 1 or 2 and reach index 4 or beyond.
Example 2
Input: nums = [3,1,3], k = 3
Output: 0
Explanation: The maximum 3 occurs only twice in the whole array.
Example 3
Input: nums = [7,7,7], k = 1
Output: 6
Explanation: Every subarray contains a 7.
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^61 <= k <= 10^5
Hints for Count Subarrays Where Max Element Appears at Least K Times
Hint 1
The element that matters is fixed: the maximum of the entire array. Only its positions affect the answer.
Hint 2
If a subarray
[l, r]contains the maximum at leastktimes, then so does every subarray[l', r]withl' <= l.Hint 3
Sweep
right; count occurrences of the maximum in the window and moveleftforward while the count is still at leastk. After that, exactlyleftstarting positions (0 .. left-1) give valid subarrays ending atright.
How to solve Count Subarrays Where Max Element Appears at Least K Times
For a fixed right end, extending to the left only adds occurrences of the maximum, so the valid left ends are a prefix 0 .. left-1. A sliding window finds left for every right end in one pass.
Approach
- Compute
M = max(nums). - Keep
left = 0andcnt = 0(occurrences ofMinnums[left..right]). - For each
right: ifnums[right] == M, incrementcnt. - While
cnt >= k: ifnums[left] == M, decrementcnt; advanceleft. - Add
leftto the answer — every start0 .. left-1still has at leastkcopies when ending atright.
Why it works
After the inner loop, [left, right] holds fewer than k copies of M, but [left - 1, right] held at least k (that is why the loop advanced past it), and so does every window starting further left. Since left never moves backwards — adding elements on the right only increases the count — the total work is linear.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The maximum is the global one; recomputing a window maximum solves a different problem.
- The answer can be quadratic in
n— accumulate it in 64-bit in fixed-width languages. - If
Moccurs fewer thanktimes overall, the loop never advances and the answer is 0, as it should be.
Reference solution
Python
from typing import List
def countSubarrays(nums: List[int], k: int) -> int:
mx = max(nums)
cnt = 0
left = 0
ans = 0
for v in nums:
if v == mx:
cnt += 1
while cnt >= k:
if nums[left] == mx:
cnt -= 1
left += 1
ans += left
return ansJava
public static int countSubarrays(int[] nums, int k) {
int mx = 0;
for (int v : nums) mx = Math.max(mx, v);
int cnt = 0, left = 0;
long ans = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == mx) cnt++;
while (cnt >= k) {
if (nums[left] == mx) cnt--;
left++;
}
ans += left;
}
return (int) ans;
}C++
int countSubarrays(vector<int>& nums, int k) {
int mx = *max_element(nums.begin(), nums.end());
int cnt = 0, left = 0;
long long ans = 0;
for (int right = 0; right < (int) nums.size(); right++) {
if (nums[right] == mx) cnt++;
while (cnt >= k) {
if (nums[left] == mx) cnt--;
left++;
}
ans += left;
}
return (int) ans;
}JavaScript
var countSubarrays = function(nums, k) {
var mx = 0;
for (var i = 0; i < nums.length; i++) if (nums[i] > mx) mx = nums[i];
var cnt = 0, left = 0, ans = 0;
for (var right = 0; right < nums.length; right++) {
if (nums[right] === mx) cnt++;
while (cnt >= k) {
if (nums[left] === mx) cnt--;
left++;
}
ans += left;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sliding Window Technique