Count Subarrays Where Max Element Appears at Least K Times

Med

#2642Time: O(N^2) in the worst case. Finding the maximum element takes O(N). The nested loops run in O(N^2) time, leading to a total complexity dominated by the loops.Space: O(1), as we only use a few variables to store the maximum value, counters, and loop indices.

Patterns

Sliding Window

Data structures

Array

Prompt

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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves systematically checking every possible contiguous subarray within the nums array. We use two nested loops to define the start and end of each subarray. For each subarray, we count the occurrences of the global maximum element and check if the count meets the k threshold.

Algorithm

First, find the maximum element maxVal in the entire nums array.
Initialize a result counter, ans, to zero.
Use a nested loop to iterate through all possible subarrays. The outer loop with index i defines the start of the subarray, and the inner loop with index j defines the end.
For each starting position i, initialize a counter currentMaxCount to 0.
As the inner loop for j progresses from i to n-1, check if nums[j] is equal to maxVal. If it is, increment currentMaxCount.
If currentMaxCount becomes greater than or equal to k, it means the subarray nums[i...j] is valid. From this point on, for this fixed i, all subsequent subarrays nums[i...j+1], nums[i...j+2], etc., will also be valid.
Therefore, once currentMaxCount >= k, we can add the remaining number of subarrays, which is n - j, to our ans and break the inner loop to move to the next i.
After iterating through all possible starting points i, ans will hold the total count.

Walkthrough

The brute-force method is the most straightforward way to solve the problem.

First, we iterate through the entire array to find its maximum element, let's call it maxVal.
We then initialize a variable ans to 0, which will store our final count of valid subarrays.
We use a pair of nested loops. The outer loop, with index i, iterates from 0 to n-1 and sets the starting point of our subarrays.
The inner loop, with index j, iterates from i to n-1, setting the ending point. This (i, j) pair defines the subarray nums[i...j].
For each subarray, we count the number of times maxVal appears. To optimize this slightly from a naive O(N^3) approach, we can maintain a running count of maxVal within the inner loop.
When the count of maxVal in nums[i...j] reaches or exceeds k, we increment our ans. A further optimization is to notice that if nums[i...j] is valid, so is nums[i...j+1], nums[i...j+2], etc. So, once a valid subarray is found, we can add all remaining extensions to the answer and break the inner loop.

1class Solution {2    public long countSubarrays(int[] nums, int k) {3        int maxVal = 0;4        for (int num : nums) {5            maxVal = Math.max(maxVal, num);6        }7 8        long ans = 0;9        int n = nums.length;10 11        for (int i = 0; i < n; i++) {12            int currentMaxCount = 0;13            for (int j = i; j < n; j++) {14                if (nums[j] == maxVal) {15                    currentMaxCount++;16                }17                if (currentMaxCount >= k) {18                    // If nums[i..j] is valid, then nums[i..j+1], nums[i..j+2], ..., nums[i..n-1] are also valid.19                    // There are (n-1) - j + 1 = n - j such subarrays.20                    ans += (n - j);21                    break; // Move to the next starting position i22                }23            }24        }25        return ans;26    }27}

Complexity

Time

O(N^2) in the worst case. Finding the maximum element takes O(N). The nested loops run in O(N^2) time, leading to a total complexity dominated by the loops.

Space

O(1), as we only use a few variables to store the maximum value, counters, and loop indices.

Trade-offs

Pros

The logic is simple and easy to understand.
It's a direct implementation of the problem statement.

Cons

The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

A much more efficient solution uses the sliding window technique. The core idea is to maintain a window [left...right] and efficiently count the number of valid subarrays as we iterate through the array with the right pointer. For each position right, we determine how many subarrays ending at right satisfy the condition.

Algorithm

First, find the maximum element maxVal in the nums array.
Initialize ans = 0, a left pointer to 0, and maxCountInWindow = 0.
Iterate through the array with a right pointer from 0 to n-1.
At each right, if nums[right] == maxVal, increment maxCountInWindow.
Now, use a while loop to shrink the window from the left. As long as the current window [left...right] is valid (i.e., maxCountInWindow >= k), we shrink it by incrementing left. If the element at the old left position was maxVal, we decrement maxCountInWindow.
After the while loop finishes, left points to the first index p such that the window [p...right] has fewer than k maximum elements. This implies that any subarray ending at right with a starting index i from 0 to p-1 is a valid subarray.
The number of such valid starting indices is p, which is the current value of left. So, we add left to our total ans.
Repeat this for all right pointers.
Return ans.

Walkthrough

This optimal approach leverages a sliding window to achieve linear time complexity. Instead of re-calculating for every subarray, we maintain a window and update our counts as the window slides.

The key insight is to count, for each ending position right, how many valid subarrays [i...right] exist. A subarray is valid if it has at least k occurrences of the array's maximum element (maxVal).

We use two pointers, left and right, to define our sliding window. We expand the window by moving right one step at a time. If nums[right] is maxVal, we increment a counter for maxVal within the window.

Whenever our window [left...right] becomes 'valid' (i.e., contains k or more maxVals), we know that any subarray starting at an index i <= left and ending at right is also valid. To simplify counting, we can find the minimal valid window.

A cleaner way to count is to observe the following: for a fixed right, we advance left as much as possible while the window [left...right] remains valid. Let's say we stop at left = p. This means any subarray starting at 0, 1, ..., p-1 and ending at right is a valid subarray. There are p such subarrays. So, for each right, we add the current left pointer's value to our answer.

1class Solution {2    public long countSubarrays(int[] nums, int k) {3        int maxVal = 0;4        for (int num : nums) {5            maxVal = Math.max(maxVal, num);6        }7 8        long ans = 0;9        int left = 0;10        int maxCountInWindow = 0;11        int n = nums.length;12 13        for (int right = 0; right < n; right++) {14            if (nums[right] == maxVal) {15                maxCountInWindow++;16            }17 18            // While the window is valid (has at least k max elements),19            // shrink it from the left to find the boundary.20            while (maxCountInWindow >= k) {21                if (nums[left] == maxVal) {22                    maxCountInWindow--;23                }24                left++;25            }26            27            // For the current 'right', any subarray ending at 'right' with a starting28            // index from 0 to 'left - 1' is a valid subarray. The number of such29            // starting points is 'left'.30            ans += left;31        }32 33        return ans;34    }35}

Complexity

Time

O(N). Finding the maximum element is O(N). The main loop involves two pointers, `left` and `right`, each traversing the array at most once. This results in a total time complexity of O(N).

Space

O(1), as it only requires a few variables for the pointers and the count, irrespective of the input size.

Trade-offs

Pros

Extremely efficient with O(N) time complexity.
Uses constant extra space, making it optimal in terms of memory usage.

Cons

The logic, while efficient, can be less intuitive to grasp initially compared to the brute-force method.

Solutions

Solution

1class Solution {2public3  long countSubarrays(int[] nums, int k) {4    int mx = Arrays.stream(nums).max().getAsInt();5    int n = nums.length;6    long ans = 0;7    int cnt = 0, j = 0;8    for (int x : nums) {9      while (j < n && cnt < k) {10        cnt += nums[j++] == mx ? 1 : 0;11      }12      if (cnt < k) {13        break;14      }15      ans += n - j + 1;16      cnt -= x == mx ? 1 : 0;17    }18    return ans;19  }20}

1class Solution {2public:3  long long countSubarrays(vector<int> &nums, int k) {4    int mx = *max_element(nums.begin(), nums.end());5    int n = nums.size();6    long long ans = 0;7    int cnt = 0, j = 0;8    for (int x : nums) {9      while (j < n && cnt < k) {10        cnt += nums[j++] == mx;11      }12      if (cnt < k) {13        break;14      }15      ans += n - j + 1;16      cnt -= x == mx;17    }18    return ans;19  }20};

1class Solution:2    def countSubarrays(self, nums: List[int], k: int) -> int: mx = max(nums) n = len(nums) ans = cnt = j = 0 for x in nums: while j < n and cnt < k: cnt += nums[j] == mx j += 1 if cnt < k: break ans += n - j + 1 cnt -= x == mx return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem