1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold Medium

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Approach

Input: An integer array arr and two integers k and threshold.

Output: Return the number of contiguous subarrays of size k whose average is at least threshold.

This problem belongs to the Fixed-length Sliding Window category.

We can maintain a sliding window of size k tracking the total sum of elements inside the window. Because the average of each subarray equals the window sum divided by k, we can precalculate a sum threshold: k * threshold. This simplifies the problem into checking if the window sum is greater than or equal to this target sum, thus avoiding repetitive division operations which might yield floats.

While iterating through the array, at each step we shift the window right by appending the new incoming element and removing the leftmost outflowing element, subsequently updating the running sum. If the running sum satisfies or exceeds the computed threshold, the active condition is fulfilled and our valid subarray counter increments.

Once the array is fully traversed, return the final iteration of the tally.

Implementation

python

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # Initial compilation block establishing values for our first subarray window
        window_sum = sum(arr[:k])
        
        # Checking condition for subarray index block 0 (using math multiplication equivalent logic instead of division)
        # Because window_sum / k >= threshold strictly correlates with window_sum >= k * threshold
        count = 1 if window_sum >= k * threshold else 0

        # Propagate sliding window commencing strictly beyond element 'k' 
        for i in range(k, len(arr)):
            # Update sequence by attaching newly included item and dropping outdated left end tail element
            window_sum += arr[i] - arr[i - k]

            # Validation stage tracking incremental updates over limit mark
            if window_sum >= k * threshold:
                count += 1

        return count  # Final viable answer tally

javascript

const numOfSubarrays = function(arr, k, threshold) {
    // Variable logging for preliminary subset span aggregating
    let windowSum = 0;

    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    // Evaluating original subset limits mapped around threshold metric constraints bounds
    // Condition verification without fractionally mapping values: windowSum >= k * threshold
    let count = windowSum >= k * threshold ? 1 : 0;

    // Extend process linearly forwards
    for (let i = k; i < arr.length; i++) {
        // Shifting sequence dynamically tracking value replacements mapped against edges
        windowSum += (arr[i] - arr[i - k]);

        // Evaluate against limiting variables and tick progress checks
        if (windowSum >= k * threshold) {
            count++;
        }
    }

    // Pass evaluated integer results 
    return count;
};

Complexity Analysis

• Time Complexity: O(n) computing via single linear iteration across the data structure
• Space Complexity: O(1) storing simple numbers for evaluations

Links

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (English)1343. 大小为 K 且平均值大于等于阈值的子数组数目 (Chinese)