0

Sliding Window

Medium

Longest subarray whose sum stays within a limit. Grow on the right, shrink on the left whenever the window breaks the rule.

variable windowlinear
TimeO(n)
SpaceO(1)
Inputnumbers | max allowed sum
2
0
1
1
5
2
1
3
3
4
2
5
4
6
sum0limit8

Longest run whose sum stays at or below 8.

adds0removes0
1 / 17
l = 0; sum = 0; best = 0
for r from 0 to n-1:
sum += a[r]
while sum > limit:
sum -= a[l]; l++
best = max(best, r - l + 1)
Why it matters

Both pointers only move right, so each index is added once and removed once.

Practise this
Minimum Size Subarray SumMLongest Substring Without Repeating CharactersMMax Consecutive Ones IIIM
Keyboard
space play← → stepr restartctrl K search

More in Sliding Window

Sliding Window Maximum
O(n)
Next visualiser
Sliding Window Maximum