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

Problem

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold

Solution: Sliding Window

First Solution

Time Complexity: O(len(arr))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
    ans = left = curr = 0
    threshold *= k
    for right in range(len(arr)):
      # do logic here to add arr[right] to curr
      curr += arr[right]

      while right - left + 1> k:
        # remove arr[left] from curr
        curr -= arr[left]
        left += 1

      # update ans
      if right - left + 1 == k and curr >= threshold:
        ans += 1
    
    return ans

Refined Solution

Time Complexity: O(len(arr))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
    ans = curr = 0
    for i in range(k - 1):
      curr += arr[i]
    threshold *= k
    for right in range(k - 1, len(arr)):
      curr += arr[right]

      # update ans
      if curr >= threshold:
        ans += 1

      curr -= arr[right - k + 1]
    
    return ans

Last Updated on 2023/09/07 by A1go