# 1343.number-of-avg-subarr-sizek-greater-or-equal-threshold

## Problem

[1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold](https://leetcode.com/contest/biweekly-contest-19/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/)

## Problem Description

```
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 = [1,1,1,1,1], k = 1, threshold = 0
 Output: 5

 Example 3:

 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.

 Example 4:

 Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
 Output: 1

 Example 5:

 Input: arr = [4,4,4,4], k = 4, threshold = 1
 Output: 1

Constraints:

  1 <= arr.length <= 10^5
  1 <= arr[i] <= 10^4
  1 <= k <= arr.length
  0 <= threshold <= 10^4
```

## Solution

This problem is pretty straigtforward, group each size k subarray, calculate avg of this group, compare avg and threshold.

Steps:

* check whether current length of arr and size k
  * if len < k, return false. not enough elements to from a group subarray of size k.
* scan arr from start position 0, each time check group a subarray of size k.
  * calculate avg of subarray of current size k \[i, i + k -1],&#x20;
  * if avg >= threshold, count + 1
  * otherwise, do nothing, continue, index i+1;
* until last pos (len - k). return count.&#x20;

For example:

![Number of Subarrays](https://388701358-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LmDY11BLFD0Iupj9U9t%2Fsync%2F9b10b03f079dc61b594d7fd68f9d5d1c3dfbb5e9.png?generation=1588973289297983\&alt=media)

### Complexity Analysis

* _Time Complexity:_ `O(n) - n is the length of arr`
* _Space Complexity:_ `O(1) - no extra space`

## Key Points

* Group each size k subarray.&#x20;
* Calculate avg of subarray of size k, compare with threshold
* Count increase 1 if meet requirements

## Code

_Java Code_

```java
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        // check len whether can form subarray of size k
        if (arr.length < k) return 0;
        int count = 0;
        int len = arr.length;
        for (int i = 0; i <= len - k; i++) {
            // if meet size of k subarray and avg >= threshold, count+1
            if (isAvgGreat(arr, i, i + k - 1, threshold)) {
                count++;
            }
        }
        return count;
    }

    private boolean isAvgGreat(int[] arr, int i, int j, int threshold) {
        long sum = 0;
        for (int k = i; k <= j; k++) {
            sum += arr[k];
        }
        return (sum / (j - i + 1)) >= threshold;
    } 
}
```
