Leetcode problem 107 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

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.

Constraints:

1 <= arr.length <= 105 1 <= arr[i] <= 104 1 <= k <= arr.length 0 <= threshold <= 104

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} threshold
 * @return {number}
 */
var numOfSubarrays = function (arr, k, threshold) {
  // Initialize a counter to store the count of valid subarrays
  let count = 0;

  // Initialize pointers 'left' and 'right' for the sliding window
  let left = 0;
  let right = k;

  // Calculate the initial sum of the first subarray
  let sum = arr.slice(left, right).reduce((a, b) => a + b, 0);

  // Iterate through the array using a sliding window approach
  while (right <= arr.length) {
    // If the window is not at the beginning of the array, adjust the sum by subtracting the leftmost element
    // and adding the rightmost element to slide the window
    if (left > 0) {
      sum -= arr[left - 1];
      sum += arr[right - 1];
    }

    // Check if the average of the current subarray is greater than or equal to the threshold
    if (sum / k >= threshold) {
      // Increment the counter if the condition is satisfied
      count++;
    }

    // Move the window by incrementing the 'left' and 'right' pointers
    left++;
    right++;
  }

  // Return the final count of valid subarrays
  return count;
};

The time complexity of this algorithm is O(n), where n is the length of the input array. This is because we iterate through the array once using a sliding window approach, and each iteration takes constant time.

The space complexity of this algorithm is O(1), as we only use a constant amount of additional space to store the count, left and right pointers, and the sum. The space used does not depend on the size of the input array.