LeetCode Daily Practice Problem : 2962. Count Subarrays Where Max Element Appears at Least K Times

Problem Statement

Number of Subarrays with Bounded Maximum

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⁵

Photo by Stephanie Cook on Unsplash

Intuition

To solve this problem, we can use the sliding window technique. We initialize and find the maximum element in the given array. Then, for each right index r, we find the subarray with k maximum elements. All subarrays bigger than it satisfy the condition. Hence, we will manipulate the left pointer to achieve this.

Approach

1. Initialize the maximum element in the array and two pointers l and r.
2. Iterate through the array with the right pointer r.
3. If the element at r is the maximum element, increment max_cnt.
4. While max_cnt is greater than k or the element at the left pointer l is not the maximum element, move the left pointer l forward and decrement max_cnt.
5. If max_cnt becomes equal to k, increment the count of subarrays by l + 1.
6. Return the count.

Time Complexity

The time complexity of this approach is O(n), where n is the size of the given array nums.

Space Complexity

The space complexity of this approach is O(1), as we are using only a constant amount of extra space.

Code

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:

        
        max_ele=max(nums)
        
        max_cnt=0
        cnt=0
        l=0
        for r in range(len(nums)):
            if nums[r]==max_ele:
                max_cnt+=1
            
            while max_cnt>k or nums[l]!=max_ele:
                if nums[l]==max_ele:
                    max_cnt-=1
                l+=1
            
            if max_cnt==k:
                
                cnt+=(l+1)
        
        return cnt

Reference

https://www.youtube.com/watch?v=CZ-z1ViskzE