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

Problem Explanation

The problem requires finding sub-arrays of a given size or length k in the given array whose average is greater than or equal to the specified threshold. A sub-array is a contiguous part of an array.

This problem can be solved using the Sliding Window approach. This is a commonly used approach for problems involving sub-arrays. It involves iterating through the array while keeping a "window" of elements, and moving this window throughout the array. In this case, the sliding window is applied to the array and a sum of the elements within the window is maintained. This sum is then divided by the window size k to calculate the average of the elements in that window. If the average is greater than or equal to the threshold, we find a valid sub-array.

Let's walk through an example:

Suppose we have an array {2,2,2,2,5,5,5,8} with k = 3 and threshold = 4. Our initial window is {2,2,2} with an average of 2, which is less than 4. We move the window to get {2,2,5} with an average of 3 which is still less than 4. Our next window is {2,5,5} with an average of 4 which is equal to 4, so this is a valid sub-array. We continue in this manner until we've reached the last sub-array of length k in the array. By moving the window in this way and checking the average at each step, we find that there are 3 sub-arrays of size k and average greater than or equal to threshold.

Python Solution

1
2python
3class Solution:
4    def numOfSubarrays(self, arr, k, threshold):
5        counts = 0
6        window_sum = 0
7
8        for i in range(len(arr)):
9            window_sum += arr[i]
10
11            # slide the window
12            if i >= k:
13                window_sum -= arr[i - k]
14
15            # calculate average of elements in the window
16            if i >= k - 1 and window_sum / k >= threshold:
17                counts += 1
18        return counts

Java Solution

1
2java
3class Solution {
4    public int numOfSubarrays(int[] arr, int k, int threshold) {
5        int counts = 0;
6        int windowSum = 0;
7
8        for (int i = 0; i < arr.length; i++) {
9          windowSum += arr[i];
10
11          // slide the window
12          if (i >= k)
13            windowSum -= arr[i - k];
14
15          // calculate average of elements in the window
16          if (i >= k - 1 && windowSum / k >= threshold)
17            counts++;
18        }
19
20        return counts;
21    }
22}

JavaScript Solution

1
2js
3class Solution {
4  numOfSubarrays(arr, k, threshold) {
5    let counts = 0;
6    let windowSum = 0;
7
8    for (let i = 0; i < arr.length; i++) {
9      windowSum += arr[i];
10
11      // slide the window
12      if (i >= k)
13        windowSum -= arr[i - k];
14
15      // calculate average of elements in the window
16      if (i >= k - 1 && windowSum / k >= threshold)
17        counts++;
18    }
19
20    return counts;
21  }
22}

C++ Solution

1
2c++
3class Solution {
4 public:
5  int numOfSubarrays(vector<int>& arr, int k, int threshold) {
6    int counts = 0;
7    int windowSum = 0;
8
9    for (int i = 0; i < arr.size(); i++) {
10      windowSum += arr[i];
11
12      // slide the window
13      if (i >= k)
14        windowSum -= arr[i - k];
15
16      // calculate average of elements in the window
17      if (i >= k - 1 && windowSum / k >= threshold)
18        counts++;
19    }
20
21    return counts;
22  }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int NumOfSubarrays(int[] arr, int k, int threshold) {
5        int counts = 0;
6        int windowSum = 0;
7
8        for (int i = 0; i < arr.Length; i++) {
9          windowSum += arr[i];
10
11          // slide the window
12          if (i >= k)
13            windowSum -= arr[i - k];
14
15          // calculate average of elements in the window
16          if (i >= k - 1 && windowSum / k >= threshold)
17            counts++;
18        }
19
20        return counts;
21    }
22}

In all these solutions, the concepts applied are the same, keeping a window of length k and computing the average by adding new element at the right end of the window and removing the oldest element from the left end. The window slides through the array from left to right. If at any time the average is greater than or equal to threshold, we increment our counter.

Keep in mind that these implementations are straightforward and should work for any valid inputs. However, please also note that they do not handle edge cases such as when the array is empty, k is greater than the length of the array or k is zero.

These conditions should ideally be checked at the beginning of the function to validate the input and return appropriate values (usually an exception or error).

Time Complexity

The time complexity for each of these solutions is O(n) where n is the length of the array. This is because we are performing a single pass through the array.

Space Complexity

The space complexity for each of these solutions is O(1). This is because we do not use any additional space that scales with the input. The variables used in the functions do not change with the size of the input array.

By applying sliding window approach, we learned how we can efficiently address problems that involve calculating a metric (like average) over a sub-array of a given length within a larger array. And we did this through multiple popular programming languages such as Python, Java, JavaScript, C++, and C#. This approach has a broad array of applications in coding interviews and competitive programming and may be applied to more complex scenarios and problems.