LeetCode 2962 - Count Subarrays Where Max Element Appears at Least K Times

The problem asks us to count subarrays in an integer array nums where the maximum element of the subarray occurs at least k times.

leetcodemediumarraysliding-window

LeetCode Problem 2962

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to count subarrays in an integer array nums where the maximum element of the subarray occurs at least k times. In other words, for every contiguous slice of the array, we need to identify the largest number in that slice and check if it appears k or more times. If it does, the subarray contributes to the final count.

The input consists of a positive integer array nums and an integer k. The output is a single integer representing the number of subarrays satisfying the condition.

The constraints indicate that nums can have up to 10^5 elements, each element up to 10^6, and k can be up to 10^5. This scale rules out naive solutions that examine all possible subarrays directly because such an approach would be O(n²) or O(n³) in time complexity.

Important edge cases to keep in mind include arrays with all identical elements, arrays where no element occurs at least k times, arrays of length 1, and cases where k is 1 (which simplifies the problem since the maximum only needs to appear once).

Approaches

Brute Force

The brute-force approach iterates over every possible subarray of nums. For each subarray, we determine the maximum element and count its occurrences. If it appears at least k times, we increment our total count. This method is correct but inefficient, with O(n³) complexity for checking all subarrays and counting occurrences, or O(n²) if using a hash map for counting within each subarray.

Optimal Approach

The key insight is that the maximum element is the only element that matters for each subarray, and we can use a sliding window approach combined with tracking positions of the maximum element. Instead of evaluating every subarray, we identify segments between elements that are strictly less than the global maximum. Within these segments, we can count valid subarrays by locating positions where the maximum appears at least k times and calculating the number of possible subarrays around those positions using combinatorial reasoning. This reduces the problem to a linear scan with some constant-time calculations per maximum occurrence, yielding O(n) time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n) Iterates all subarrays and counts occurrences
Optimal O(n) O(n) Sliding window / segment-based counting using max positions

Algorithm Walkthrough

  1. Identify the global maximum of the array. Only this value can be counted towards subarrays meeting the requirement since any other element cannot surpass it in a subarray.
  2. Initialize a variable count to store the total number of valid subarrays.
  3. Iterate through nums while maintaining a segment of elements that are less than or equal to the maximum. Whenever the maximum is found, record its position.
  4. For each segment, calculate how many subarrays contain at least k occurrences of the maximum. This can be done by treating the positions of the maximum as anchors and counting the number of subarrays starting and ending around these anchors.
  5. Sum the counts from all segments to produce the final answer.

Why it works: Every subarray that satisfies the condition must contain at least k occurrences of the maximum. By only focusing on positions of the maximum and calculating subarrays around them, we ensure all valid subarrays are counted exactly once, and we avoid redundant checks on elements that cannot influence the result.

Python Solution

from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_val = max(nums)
        count = 0
        positions = []
        
        for i, num in enumerate(nums):
            if num == max_val:
                positions.append(i)
        
        if not positions or len(positions) < k:
            return 0
        
        for i in range(len(positions) - k + 1):
            left = positions[i] - (positions[i-1] if i > 0 else -1)
            right = (positions[i+k-1+1] if i+k < len(positions) else n) - positions[i+k-1]
            count += left * right
        
        return count

The implementation first identifies all positions of the global maximum. If the number of occurrences is less than k, we can immediately return zero. For each contiguous group of k maximums, we calculate the number of subarrays that can be formed with these maximums inside using the distance to neighboring maximums or array boundaries.

Go Solution

func countSubarrays(nums []int, k int) int64 {
    n := len(nums)
    maxVal := 0
    for _, num := range nums {
        if num > maxVal {
            maxVal = num
        }
    }

    positions := []int{}
    for i, num := range nums {
        if num == maxVal {
            positions = append(positions, i)
        }
    }

    if len(positions) < k {
        return 0
    }

    var count int64 = 0
    for i := 0; i <= len(positions)-k; i++ {
        left := positions[i]
        if i > 0 {
            left -= positions[i-1]
        } else {
            left += 1
        }

        right := n - positions[i+k-1]
        if i+k < len(positions) {
            right = positions[i+k] - positions[i+k-1]
        }

        count += int64(left * right)
    }
    return count
}

In Go, we explicitly handle slice appending and integer arithmetic carefully. We also maintain an int64 for the count because the number of subarrays can be very large.

Worked Examples

Example 1: nums = [1,3,2,3,3], k = 2

Positions of max 3: [1, 3, 4]

  • Subarrays with first 2 max positions: left options = 2 (1 or 0), right options = 3 (3, 4, end) → 2 * 3 = 6
  • Subarrays with last 2 max positions: left = 2 (3, 4), right = 1 → 2 * 1 = 2

Total subarrays: 6 (matches expected output).

Example 2: nums = [1,4,2,1], k = 3

Positions of max 4: [1]

Less than k, so output = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Scan array to find max and positions of max, then compute subarrays in a single pass
Space O(n) Store positions of max elements

The time complexity is linear because we never revisit elements unnecessarily. Space complexity is linear in the worst case when all elements are equal to the maximum.

Test Cases

# test cases
assert Solution().countSubarrays([1,3,2,3,3], 2) == 6  # example 1
assert Solution().countSubarrays([1,4,2,1], 3) == 0     # example 2
assert Solution().countSubarrays([1,1,1,1], 2) == 6    # all same elements
assert Solution().countSubarrays([5,1,5,1,5], 1) == 9  # k=1, maximum appears multiple times
assert Solution().countSubarrays([1], 1) == 1          # single element
assert Solution().countSubarrays([1,2,3,4,5], 1) == 1  # max is last element
assert Solution().countSubarrays([2,2,2,2,2], 5) == 1  # max occurs exactly k times
Test Why
[1,3,2,3,3], k=2 Basic example with multiple valid subarrays
[1,4,2,1], k=3 No subarray has enough max occurrences
[1,1,1,1], k=2 All elements same, multiple overlapping subarrays
[5,1,5,1,5], k=1 Minimum k, multiple max positions
[1], k=1 Single-element array
[1,2,3,4,5], k=1 Max at the end of array
[2,2,2,2,2], k=5 Max occurs exactly k times

Edge Cases

One important edge case is when k is larger than the number of occurrences of the maximum element. In this case, the solution must return zero, as no subarray can satisfy the requirement. Our implementation checks this explicitly.

Another edge case is arrays of length 1. Any single-element array where k = 1 is trivially a valid subarray. Our implementation naturally handles this by using array indices for subarray calculation.

A third edge case is when all elements in nums are the same. This can produce a large number of overlapping subarrays. Using the combinatorial counting of left and right options around positions of the maximum ensures that all valid subarrays are counted