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.

Examples

Example 1:

1
2
3

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:

1
2
3

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^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= 10^5

Solution

Method 1 - Sliding window

Here is the approach:

  1. Identify the Maximum Element:
    • Compute the maximum value in the array since only subarrays containing this element are relevant.
  2. Sliding Window Logic:
    • Use two pointers (start and end) to maintain a sliding window across the array.
    • Within the window:
      • Count how many times the maximum element appears.
    • If the count of the maximum element equals k:
      • Shrink the window (start++) until the count becomes less than k.
      • At this point, all subarrays starting from position start to end are valid, and we increment our result (ans).
  3. Accumulate Results:
    • Add the size of the valid range (calculated as start) to the final result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {

    public long countSubarrays(int[] nums, int k) {
        // Step 1: Find the maximum element in the array
        int maxElement = Arrays.stream(nums).max().getAsInt();
        long ans = 0;
        int start = 0;
        int maxCount = 0; // Count occurrences of the maximum element in the current window

        // Step 2: Sliding window logic
        for (int end = 0; end < nums.length; end++) {
            if (nums[end] == maxElement) {
                maxCount++;
            }

            while (maxCount == k) { // Shrink window if maxElement count equals k
                if (nums[start] == maxElement) {
                    maxCount--;
                }
                start++;
            }

            ans += start; // Count valid subarrays ending at 'end'
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_element = max(nums)  # Step 1: Identify the maximum element
        ans = 0
        start = 0
        max_count = 0  # Tracks occurrences of max_element in the current window

        # Step 2: Sliding window logic
        for end in range(len(nums)):
            if nums[end] == max_element:
                max_count += 1

            while max_count == k:  # Shrink window if max_element count equals k
                if nums[start] == max_element:
                    max_count -= 1
                start += 1

            ans += start  # Count valid subarrays ending at 'end'

        return ans

Complexity

  • ⏰ Time complexity: O(n): We traverse the array once using the end pointer. The start pointer also progresses in a single pass over the array during adjustments.
  • 🧺 Space complexity: O(1): No extra space is used beyond a few variables, as all computations are performed directly on the input array.