Problem Informations

• Problem Index: 2962
• Problem Link: Count Subarrays Where Max Element Appears at Least K Times
• Topics: Array, Sliding Window

Problem Description

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 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^6$
• $1 \leq k \leq 10^5$

Intuition

The core problem involves identifying subarrays from a given array nums where the maximum element appears at least k times. Upon analysis, one can observe that the task boils down to managing occurrences of the maximum element within potential subarrays using an efficient searching strategy.

Approach

To tackle this problem, we utilize a two-pointer approach which efficiently scans through the array to check for qualifying subarrays. Here is a breakdown of the steps:

1. Identify the Maximum Element: First, find the maximum element in the array nums. This can be done in $O(n)$ time by scanning through the array once.

2. Initialize Counters: Set up variables to keep track of occurrences of the maximum element (count) and the total count of valid subarrays (result). Both counters are initialized to zero.

3. Two-Pointer Technique: We employ a two-pointer technique, which involves maintaining a window with two indices (left and right) that explore potential subarrays.

   • Start with both pointers at the beginning of the array. Increment the right pointer step by step, expanding the window to include each new element.

   • Upon encountering an element equal to the maximum element, increment the count.

4. Adjust Left Boundary: Move the left pointer when the subarray contains more than k occurrences of the maximum element to ensure that the subarray starts at the earliest possible position. This ensures that count remains valid, i.e., holds the occurrences of the maximum element within the current window.

5. Counting Valid Subarrays: For every position of the right pointer, if the number of maximum elements (count) is greater than or equal to k, every subarray starting from indices 0 through left up to right will be valid. We add the number of such subarrays (left + 1) to result.

6. Iterate Through Entire Array: Continue this process until the right pointer has traversed the entire array, ensuring that all subarrays are considered.

This approach efficiently manages the constraint of ensuring at least k instances of the maximum element within subarrays, and runs with a time complexity of $O(n)$, which is optimal given the constraints.

Code

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        // Identify the maximum element in the array
        long long maxElement = *max_element(nums.begin(), nums.end());
        
        // Initialize counters for counting the occurrences and the result
        long long count = 0, result = 0;
        
        // Two pointers technique to explore all subarrays
        for (int left = 0, right = 0; right < nums.size(); right++) {
            // Increment count if the current element is the maximum element
            count += nums[right] == maxElement;
            
            // Adjust the left boundary to have at least 'k' maximum elements
            while (count - (nums[left] == maxElement) >= k) {
                count -= nums[left++] == maxElement;
            }
            
            // If current subarray has at least 'k' max elements, count all subarrays ending at right
            if (count >= k) {
                result += left + 1;
            }
        }
        
        return result;
    }
};

Python

class Solution:
    def countSubarrays(self, nums, k):
        # Identify the maximum element in the array
        maxElement = max(nums)
        
        # Initialize counters for counting the occurrences and the result
        count = 0
        result = 0
        
        # Two pointers technique to explore all subarrays
        left = 0
        for right in range(len(nums)):
            # Increment count if the current element is the maximum element
            count += nums[right] == maxElement
            
            # Adjust the left boundary to have at least 'k' maximum elements
            while count - (nums[left] == maxElement) >= k:
                count -= nums[left] == maxElement
                left += 1
            
            # If current subarray has at least 'k' max elements, count all subarrays ending at right
            if count >= k:
                result += left + 1
        
        return result

Complexity

• Time complexity: $O(n)$

  The solution utilizes a two-pointer approach, where the right pointer iterates over the array, and the left pointer adjusts to maintain the condition that the current subarray has at least k occurrences of the maximum element. Moving the left pointer ensures that each element is considered a constant number of times, making the traversal of each element of the array effectively constant work per element. Thus, the time complexity is governed by the single pass through the array, and is $O(n)$, where $n$ is the number of elements in the input array nums.

• Space complexity: $O(1)$

  The space complexity is constant, $O(1)$, as the solution only uses a fixed amount of additional space regardless of the input size. Specifically, variables such as maxElement, count, result, and the indices left and right are used, all of which occupy constant space independent of the array size. No additional data structures that scale with input size are used.