Introduction

In this blog post, we will explore how to solve the LeetCode problem "1343" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Constraints: 1 <= arr.length <= 105 1 <= arr[i] <= 104 1 <= k <= arr.length 0 <= threshold <= 104

Explanation

• Sliding Window: Calculate the sum of the first k elements. Then, slide the window of size k through the array, updating the sum by subtracting the element leaving the window and adding the element entering the window.
  • Compare Average with Threshold: In each iteration, check if the average of the current window (sum/k) is greater than or equal to the threshold. If it is, increment the count.
  • Avoid Division in the Loop: Instead of calculating the average by dividing by k in each iteration, compare the current window sum with threshold * k. This improves efficiency by avoiding floating-point division inside the loop.

• Runtime Complexity: O(n), where n is the length of the array. Storage Complexity: O(1).

Code

    def numOfSubarrays(arr: list[int], k: int, threshold: int) -> int:
    """
    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.

    Constraints:
    1 <= arr.length <= 105
    1 <= arr[i] <= 104
    1 <= k <= arr.length
    0 <= threshold <= 104
    """
    n = len(arr)
    count = 0
    window_sum = sum(arr[:k])
    threshold_sum = threshold * k

    if window_sum >= threshold_sum:
        count += 1

    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum >= threshold_sum:
            count += 1

    return count