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

MediumView on LeetCode

Array Sliding Window

Time: O(n)

Space: O(k)

Intuition

Count subarrays with exactly k distinct values where each distinct value appears at least k times. Sliding window.

Algorithm

1Count subarrays where max element count >= k. Sliding window: when any element count >= k, count subarrays.

Common Pitfalls

•Count subarrays where maximum frequency >= k. For each right endpoint, binary search or track counts.

2962.cs

// Approach: Sliding window; track positions of max element; shrink left so count stays ≥ k.
// Time: O(n) Space: O(k)

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

        int l = 0, r = 0, freq = 0;
        long ans = 0;
        while (r < n)
        {
            if (nums[r] == max)
                freq++;

            while (freq >= k)
            {
                ans += (n - r);
                if (nums[l] == max)
                    freq--;
                l++;
            }
            r++;
        }

        return ans;
    }
}

Was this solution helpful?