Sliding Window: Return the number of sub array size k that is greater than or equal to threshold

Problem Statement:

You are given an array and a subarray of size k and threshold value.

You need to find number of subarray with average greater or equal to threshold.

Example:

Input: arr = [4, 2, 6, 10] k = 2, threshold = 4

Output: 2

Solution Explanation:

We will use sliding window approach to solve this problem.

For each window form a average and check if it satisfies the condition.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;


int solution(vector<int> &arr, int k, int threshold) 
{
    int window_sum = 0;
    int count = 0;

    //calculate for the first window sum
    for(int i = 0 ; i < k ; ++i)
        window_sum += arr[i];

    for(int i = 0 ; i < arr.size() - k + 1 ; ++i)
    {
        if(i != 0)
        {
            window_sum -= arr[i - 1]; 
            window_sum += arr[i + k - 1]; 
            // new window is ready
        }
        
        int window_average = window_sum / k;
        
        if(window_average >= threshold)
            count++;
    }
    
    return count;
    
}

int main()
{

    int k = 2;
    int threshold = 4;
    vector<int> arr = { 4, 2, 6, 10 };

    cout << solution(arr, k, threshold);
}

Output

2