Scale Engineer

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 <= 105
  • 1 <= nums[i] <= 106
  • 1 <= k <= 105

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.

  1. First, we iterate through the entire array to find its maximum element, let's call it maxVal.
  2. We then initialize a variable ans to 0, which will store our final count of valid subarrays.
  3. 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.
  4. 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].
  5. 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.
  6. 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.
class Solution {    public long countSubarrays(int[] nums, int k) {        int maxVal = 0;        for (int num : nums) {            maxVal = Math.max(maxVal, num);        }         long ans = 0;        int n = nums.length;         for (int i = 0; i < n; i++) {            int currentMaxCount = 0;            for (int j = i; j < n; j++) {                if (nums[j] == maxVal) {                    currentMaxCount++;                }                if (currentMaxCount >= k) {                    // If nums[i..j] is valid, then nums[i..j+1], nums[i..j+2], ..., nums[i..n-1] are also valid.                    // There are (n-1) - j + 1 = n - j such subarrays.                    ans += (n - j);                    break; // Move to the next starting position i                }            }        }        return ans;    }}

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.

Solutions

class Solution {public  long countSubarrays(int[] nums, int k) {    int mx = Arrays.stream(nums).max().getAsInt();    int n = nums.length;    long ans = 0;    int cnt = 0, j = 0;    for (int x : nums) {      while (j < n && cnt < k) {        cnt += nums[j++] == mx ? 1 : 0;      }      if (cnt < k) {        break;      }      ans += n - j + 1;      cnt -= x == mx ? 1 : 0;    }    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 →

Next problem