Variable-Size Windows: longest valid range

Core18 min
Given an array of positive integers nums and a positive integer limit, return the length of the longest contiguous subarray whose sum is at most limit.

For nums = [2, 1, 5, 1, 3] and limit = 7, the first two values form a valid window with sum 3. Adding 5 raises the sum to 8. How far must left move to make the window valid again while keeping it as long as possible?

All values are positive. Once adding nums[right] makes the sum exceed limit, moving right farther cannot help because it would add another positive value. The window can become valid only by removing values from the left.

Remove nums[left] and advance left until the sum is at most limit. This requires a while loop because one removal may not reduce the sum enough.

Find the longest window with sum at most 7

1 / 8
window_sum
2
best_length
1
status
valid
Step 1 of 8.
Start with left and right at index 0. The one-value window [2] is valid, so best_length starts at 1.
  • current window
  • value removed

When the loop stops, left is the earliest remaining start that gives a valid window ending at right. Any start already passed by left was ruled out when its window exceeded the limit, and adding later positive values cannot make that earlier start valid again.

Only then compare right - left + 1 with the best length found so far. Updating before the shrinking finishes would record a window whose sum is still too large.

Why should shrinking stop as soon as window_sum <= limit?

If one value is larger than limit, the loop removes that value too. Then left == right + 1, the current window is empty, and its candidate length is 0. The code handles this without a special case.

1def longest_bounded_sum(nums: list[int], limit: int) -> int:
2 left = 0
3 window_sum = 0
4 best_length = 0
5
6 for right, value in enumerate(nums):
7 window_sum += value
8
9 while window_sum > limit:
10 window_sum -= nums[left]
11 left += 1
12
13 best_length = max(best_length, right - left + 1)
14
15 return best_length
Time: O(n)Space: O(1)

right moves across the array once, and left also moves only forward across the array once. Even though one expansion may shrink several times, there are at most n total left-pointer moves, so the total time is O(n). The algorithm stores only the boundaries, current sum, and best length, giving O(1) auxiliary space.