Sliding Window Technique - Part 12

The control pointer here is the left (slow) pointer. There is probably some optimization that can be done to jump the left pointer far ahead if needed, but even with the slow movement one can achieve O(N) (in 2*N). Code is down below, cheers, ACC.

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

2962. Count Subarrays Where Max Element Appears at Least K Times

Medium

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

Accepted

16,450

Submissions

36,607

public long CountSubarrays(int[] nums, int k)
{
    int max = nums.Max();

    int left = 0;
    int right = 1;
    int countMax = nums[left] == max ? 1 : 0;
    long retVal = 0;

    while (left < nums.Length)
    {
        if (countMax >= k)
        {
            retVal += (nums.Length - right + 1);
            if (nums[left] == max) countMax--;
            left++;
        }
        else
        {
            if (right >= nums.Length)
            {
                if (nums[left] == max) countMax--;
                left++;
            }
            else
            {
                if (nums[right] == max) countMax++;
                right++;
            }
        }
    }

    return retVal;
}