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

[mah-shamim]

Topics: Array, Sliding Window

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

[mah-shamim]

We need to count the number of subarrays where the maximum element of the given array appears at least K times. The approach involves identifying the positions of the maximum element and using these positions to efficiently calculate valid subarrays.

Approach

1. Identify the Maximum Element: First, determine the maximum element in the array, as this element must appear at least K times in each valid subarray.
2. Track Indices of Maximum Element: Collect the indices where the maximum element occurs. These indices will help in determining valid subarrays.
3. Sliding Window Technique: Use the indices of the maximum element to determine valid subarrays. For each possible end position of a subarray (determined by the K-th occurrence of the maximum element), calculate the number of valid starting positions and ending positions to form valid subarrays.

Let's implement this solution in PHP: 2962. Count Subarrays Where Max Element Appears at Least K Times

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function countSubarrays($nums, $k) {
    $max = max($nums);
    $indices = array();
    foreach ($nums as $i => $num) {
        if ($num == $max) {
            $indices[] = $i;
        }
    }
    $m = count($indices);
    if ($m < $k) {
        return 0;
    }
    $n = count($nums);
    $total = 0;
    for ($j = $k - 1; $j < $m; $j++) {
        $i = $j - $k + 1;
        $prev = ($i > 0) ? $indices[$i - 1] : -1;
        $left = $indices[$i] - $prev;
        $right = $n - $indices[$j];
        $total += $left * $right;
    }
    return $total;
}

// Example Usage:
echo countSubarrays([1,3,2,3,3], 2); // Output: 6
echo "\n";
echo countSubarrays([1,4,2,1], 3);   // Output: 0
?>

Explanation:

1. Identify Maximum Element: The maximum element is found using the max function.
2. Collect Indices: The indices where the maximum element occurs are stored in an array.
3. Check Feasibility: If the number of occurrences of the maximum element is less than K, return 0 immediately.
4. Calculate Valid Subarrays: For each valid end position (starting from the K-th occurrence of the maximum element), compute the number of valid starting positions and ending positions. The number of valid starting positions is determined by the gap between consecutive occurrences of the maximum element. The number of valid ending positions is determined by the remaining elements from the current position to the end of the array.

This approach efficiently counts all valid subarrays using the positions of the maximum element, ensuring that each subarray meets the requirement of containing the maximum element at least K times. The complexity is linear with respect to the number of elements in the array, making it efficient for large input sizes.

[topugit]

Thanks for solving the problem of "Count Subarrays Where Max Element Appears at Least K Times"

[mah-shamim]

Thanks