# Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold)
Canonical: https://scaleengineer.com/dsa/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
**Companies:** [Turo](https://scaleengineer.com/companies/turo)
---
## 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 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`

# Approaches
## Brute Force Approach
The brute-force approach is the most straightforward way to solve the problem. We can generate every possible contiguous subarray of size `k`, calculate its sum, find the average, and then check if this average is greater than or equal to the given `threshold`. We use a counter to keep track of how many such subarrays we find.
**Time:** O(N * K), where N is the length of `arr`. The outer loop runs `N - K + 1` times, and for each of these iterations, the inner loop runs `K` times to compute the sum. This results in a quadratic time complexity in the worst case (when K is close to N/2). · **Space:** O(1). We only use a few variables to store the count, sum, and loop indices, which does not depend on the input size.
**Pros:** Very simple to understand and implement.; It's a good starting point for understanding the problem.
**Cons:** This approach is inefficient because it re-calculates the sum of elements for overlapping parts of consecutive subarrays.; For large inputs, this will likely result in a 'Time Limit Exceeded' (TLE) error on coding platforms.
### Explanation
We use a nested loop structure. The outer loop iterates from the beginning of the array to the last possible starting point for a subarray of size `k` (which is `arr.length - k`). The inner loop then iterates `k` times from the starting point determined by the outer loop to calculate the sum of the current subarray's elements. 

An important optimization is to avoid floating-point division inside the loop. The condition `(sum / k) >= threshold` can be rewritten as `sum >= k * threshold`. This allows us to work entirely with integers (or long, to be safe from overflow, though not strictly necessary with the given constraints).

```java
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int count = 0;
        long targetSum = (long) k * threshold;
        int n = arr.length;

        // Iterate through all possible starting points of a subarray of size k
        for (int i = 0; i <= n - k; i++) {
            long currentSum = 0;
            // Calculate the sum of the subarray starting at i
            for (int j = i; j < i + k; j++) {
                currentSum += arr[j];
            }

            // Check if the average condition is met
            if (currentSum >= targetSum) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through the array with an index `i` from 0 up to `arr.length - k`. This index `i` will be the starting point of each subarray.
- For each `i`, start a nested loop to iterate from `j = i` to `j = i + k - 1` to traverse the elements of the current subarray.
- Calculate the `sum` of the elements in this subarray.
- After calculating the sum, check if the average (`sum / k`) is greater than or equal to the `threshold`. To avoid floating-point arithmetic, this is equivalent to checking if `sum >= k * threshold`.
- If the condition is true, increment the `count`.
- After the outer loop finishes, return the `count`.

## Sliding Window Approach
A much more efficient solution uses the sliding window technique. This approach avoids the redundant calculations of the brute-force method. We maintain a 'window' of size `k` and a running sum of its elements. As we slide this window across the array, we can update the sum in constant time by subtracting the element that's leaving the window and adding the new element that's entering. This reduces the overall time complexity from quadratic to linear.
**Time:** O(N), where N is the length of `arr`. We perform a single pass to calculate the initial window sum (O(K)) and another single pass to slide the window through the rest of the array (O(N-K)). The total time is O(K + N - K) = O(N). · **Space:** O(1). We only use a few variables for the window sum, count, and loop index, which requires constant extra space.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; This is the optimal solution for this problem.
**Cons:** Slightly more complex to conceptualize than the brute-force method, though it's a very common and essential pattern.
### Explanation
The core idea is to maintain the sum of a `k`-sized window as it slides over the array. We start by computing the sum of the very first subarray (from index 0 to `k-1`). We check if this initial subarray meets the condition. Then, we iterate from the `k`-th element to the end of the array. In each step, instead of re-calculating the sum of the new window from scratch, we update the previous sum. The new sum is simply `previous_sum - element_leaving_from_left + element_entering_from_right`. This update operation takes constant O(1) time. We check the condition for each new window sum and update our count accordingly.

```java
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int count = 0;
        long windowSum = 0;
        long targetSum = (long) k * threshold;
        int n = arr.length;

        // Calculate the sum of the first window
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        // Check the first window
        if (windowSum >= targetSum) {
            count++;
        }

        // Slide the window across the rest of the array
        for (int i = k; i < n; i++) {
            // Update the window sum in O(1)
            windowSum += arr[i] - arr[i - k];
            
            // Check the new window
            if (windowSum >= targetSum) {
                count++;
            }
        }

        return count;
    }
}
```
### Algorithm
- First, calculate the required sum `targetSum = k * threshold` to avoid floating-point arithmetic.
- Initialize a `windowSum` by summing the first `k` elements of the array.
- Initialize a counter `count` to 0.
- Check if the initial `windowSum` is greater than or equal to `targetSum`. If it is, increment `count`.
- Iterate from index `k` to the end of the array (`i` from `k` to `arr.length - 1`). This loop slides the window one position at a time.
- In each iteration, update `windowSum` by adding the new element entering the window (`arr[i]`) and subtracting the element leaving the window (`arr[i - k]`).
- After updating `windowSum`, check if it's greater than or equal to `targetSum`. If it is, increment `count`.
- After the loop completes, return the final `count`.

# Solutions
### Java

```java
class Solution { public int numOfSubarrays ( int [] arr , int k , int threshold ) { int s = 0 ; for ( int i = 0 ; i < k ; ++ i ) { s += arr [ i ]; } int ans = s / k >= threshold ? 1 : 0 ; for ( int i = k ; i < arr . length ; ++ i ) { s += arr [ i ] - arr [ i - k ]; ans += s / k >= threshold ? 1 : 0 ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int numOfSubarrays ( vector < int >& arr , int k , int threshold ) { int s = accumulate ( arr . begin (), arr . begin () + k , 0 ); int ans = s >= k * threshold ; for ( int i = k ; i < arr . size (); ++ i ) { s += arr [ i ] - arr [ i - k ]; ans += s >= k * threshold ; } return ans ; } };
```

### Python

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