2Brute2Best
🔥0

Number of Sub-arrays of Size K and Average ≥ Threshold

Medium·LeetCode #1343 Pro OnlySlight Variation
LeetCode
01

Problem Statement

You are given an integer array arr, a window size k and a number threshold.

Look at every contiguous block of exactly k elements. Count how many of these blocks have an average that is at least threshold.

Input

An integer array arr, and integers k and threshold.

Output

An integer: the number of size-k subarrays whose average is ≥ threshold.

Example 1
Input: arr = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4
Output: 3

The blocks [2,5,5], [5,5,5] and [5,5,8] have averages 4, 5 and 6. Every other size-3 block has an average below 4.

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

The first 6 blocks of size 3 all have an average above 5. The last two, [7,5,2] and [5,2,3], do not.

Constraints
  • • 1 ≤ arr.length ≤ 10^5
  • • 1 ≤ arr[i] ≤ 10^4
  • • 1 ≤ k ≤ arr.length
  • • 0 ≤ threshold ≤ 10^4
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sub-arrays of size k”
→ Fixed window of size k.
“number of”
→ The answer is a count: add 1 for each window that passes, instead of keeping a max.
“average greater than or equal to threshold”
→ Fixed k → test sum ≥ threshold · k, no division needed.
03

Approach Complexity Ladder

Brute Force — sum every block and test itO(N · K)O(1)

Recompute each block's sum and compare with threshold · k

Optimal — fixed sliding window + counterO(N)O(1)

Slide one running sum; count windows with sum ≥ threshold · k

Brute Force Intuition

For every start index, add up the k elements of that block from scratch. If the sum is at least threshold · k, count it.

Recognition rule for this sub-pattern:

Window size is fixed at K. Each slide adds one element on the right and removes one on the left — update the aggregate in O(1).
Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track
C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track
Maximum Average Subarray IPermutation in String