Lets Code Everyday - Day 28

Question - 28:

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

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.

Approach taken:

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {

        int sum=0;
        int avg=0;
        int count=0;
        for(int i=0;i<k;i++){
           sum=sum+arr[i];
        }
        avg=sum/k;
        if(avg>=threshold) count++;

        for(int i=k;i<arr.length;i++){
            avg=0;
            sum=sum-arr[i-k]+arr[i];
            avg=sum/k;
            if(avg>=threshold) count++;

        }
    return count;    
    }
}

Step-by-step implementation:

1. Initialize the variables sum, avg, and count to 0.

2. Loop through the first k elements of the array arr, and add their values to the variable sum.

3. Calculate the average of the first k elements of arr and store it in the variable avg. If the avg is greater than or equal to threshold, increment the variable count by 1.

4. Loop through the remaining elements of the array arr starting from the kth element. For each iteration of the loop, subtract the value of the element i-k from the variable sum and add the value of the element i to sum. This effectively shifts the window of length k one position to the right. Calculate the new average of the elements in the current window and store it in the variable avg. If the avg is greater than or equal to threshold, increment the variable count by 1.

5. Return the value of the variable count.

In summary, the method counts the number of subarrays of length k in arr with an average value greater than or equal to threshold using a sliding window approach.

what is sliding window approach?

A sliding window approach is a technique used in computer science for efficiently processing a set of data elements, such as an array or a string. The idea behind the sliding window approach is to create a window of fixed size and slide it over the data structure, one element at a time, to process each subarray or substring.

In the case of an array, the window is simply a contiguous block of elements of fixed length. By sliding the window over the array, we can process each subarray of fixed length without iterating through each element of the array separately.

The sliding window approach is often used to solve problems that involve finding a subset of the data that satisfies a particular condition, such as finding a subarray of maximum sum or finding a substring of a certain length that contains all unique characters.

The advantage of using a sliding window approach is that it allows us to process the data elements in a single pass, without having to recompute the same values multiple times. This can lead to significant improvements in time complexity, especially for large datasets.

The time complexity of the given code is O(n), where n is the length of the input array arr. This is because we are iterating through the array twice, once to initialize the window and calculate the first average, and then again to slide the window and calculate the averages of the subsequent subarrays.

The space complexity of the code is O(1), because we are only using a constant amount of extra space to store the variables sum, avg, and count, and we are not using any additional data structures or arrays. Therefore, the space used by the algorithm does not depend on the size of the input array arr.

Thanks for reading...Happy learning...😊