Problem Statement in English

You’re given an array arr, and integers k, and threshold.

Your task is to return the number of subarrays of size k, that have an average >= threshold.

Approach

This problem is a slight variation to another one that I’ve covered.

The only difference here is that we also maintain the sum of the current window so that we don’t use a separate loop to calcuate its sum each time.

Solution in Python


class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # count the number of subarrays
        # that satisfy the given criterion here
        ans = 0

        # left pointer
        leftPtr = 0
        # we store the current sum of the window's contents here
        currentSum = 0

        for rightPtr in range(len(arr)):
            # right - left + 1 gives us the size of the current window
            #
            # if the current windows size > `k`
            if rightPtr - leftPtr + 1 > k:
                # remove value pointed to by left pointer
                currentSum -= arr[leftPtr]
                # move left pointer ahead
                leftPtr += 1
            # add value pointer to by right pointer to `currentSum`
            currentSum += arr[rightPtr]
            # if the current window size is acceptable
            if rightPtr - leftPtr + 1 == k:
                # compute current average
                # check if it's >= `threshold`
                if currentSum / k >= threshold:
                    # if it is, increment `ans`
                    ans += 1

        # return `ans`
        return ans

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only store a couple integer variables.

And we are done.