Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold — LeetCode 1343 Python Solution

MediumArraySliding Window

Problem: #1343
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

The problem

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

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).

Python solution

Python

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        s = sum(arr[:k])
        ans = int(s >= threshold)
        for i in range(k, len(arr)):
            s += arr[i] - arr[i - k]
            ans += int(s >= threshold)
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array `arr`
Space	O(1) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?: LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is rated Medium on LeetCode.
What is the time complexity of LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?: The Python solution on this page runs in O(n), where n is the length of the array `arr`.
What is the space complexity of LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold cover?: LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is tagged Array and Sliding Window on LeetCode.