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

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

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.

A sub-array is a contiguous sequence of elements within an array. The average of a sub-array is the sum of all elements divided by the number of elements.

Note: The average should be calculated as a floating-point number, but the comparison with threshold should handle integer arithmetic to avoid precision issues.

Input & Output

Example 1 — Basic Case

$ Input: arr = [2,4,2,1,5], k = 3, threshold = 2

› Output: 2

💡 Note: Sub-array [2,4,2] has average (2+4+2)/3 = 2.67 ≥ 2. Sub-array [4,2,1] has average (4+2+1)/3 = 2.33 ≥ 2. Sub-array [2,1,5] has average (2+1+5)/3 = 2.67 ≥ 2. However, only first two qualify, so answer is 2.

Example 2 — All Valid

$ Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5

› Output: 6

💡 Note: Most sub-arrays of size 3 have averages well above 5, so multiple sub-arrays qualify.

Example 3 — None Valid

$ Input: arr = [1,1,1,1,1], k = 1, threshold = 2

› Output: 0

💡 Note: All elements are 1, which is less than threshold 2, so no sub-arrays qualify.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁴
1 ≤ k ≤ arr.length
0 ≤ threshold ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4,2,1,5], k=3, threshold=2

Process

Check each sub-array of size 3 for average ≥ 2

Output

Count of valid sub-arrays = 2

Key Takeaway

🎯 Key Insight: Use sliding window to avoid recalculating sums - just add new element and remove old element

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to use sliding window technique instead of recalculating sums. Best approach is sliding window which maintains a running sum and slides efficiently. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Use sliding window technique to avoid recalculating sums
Brute Force	O(n×k)	O(1)	Check every sub-array of size k and calculate its average

Sliding Window — Algorithm Steps

Calculate sum of first k elements
For each subsequent position, slide window: subtract left element, add right element
Check if current sum gives average >= threshold
Count valid windows

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Window

Calculate sum of first k elements: 2+4+2=8

Slide Right

Remove 2, add 1: 8-2+1=7

Continue Sliding

Keep updating sum efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int n, int k, int threshold) {
    if (n < k) return 0;
    
    int count = 0;
    // Calculate sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    // Check first window
    if (windowSum >= threshold * k) {
        count++;
    }
    
    // Slide the window
    for (int i = k; i < n; i++) {
        // Remove leftmost element, add rightmost element
        windowSum = windowSum - arr[i - k] + arr[i];
        
        // Check if current window is valid
        if (windowSum >= threshold * k) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k, threshold;
    scanf("%d", &k);
    scanf("%d", &threshold);
    
    int result = solution(arr, n, k, threshold);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element added and removed exactly once

✓ Linear Growth

Space Complexity

O(1)

Only using variables for current sum and count

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler