Leetcode 1343: Number of sub-arrays of size k and average greater than or equal to threshold

In this Leetcode problem. The question is pretty much in the title:

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.

This is a typical sliding window problem. There are O(n) subarrays of size k, more exactly, there are n-k-1 such subarrays.

But, generating each subarray individually would take O(n*k) and is inefficient. Therefore, by only removing one element and adding one element for each calculation, we find an algorithm in O(n) time.

Here is the code with some comments

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.length;
        if (k > n) {
            // edge case, no subarray
            return 0;
        }
        int totalThreshold = k * threshold;
        int sum = 0;
        // generate first subarray
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }
        int res = 0;
        if (sum >= totalThreshold) {
            res++;
        }
        int next = k;
        while (next < n) {
            // add new element
            sum += arr[next];
            // remove element not anymore in the window
            sum -= arr[next - k];
            // update res
            if (sum >= totalThreshold) {
                res++;
            }…