Sliding window

Algorithm templates

Read the invariant, adapt a tested implementation and try a related problem.

Sliding window

Maintain a valid contiguous interval.

Interview essentials

When to use it

Find the longest contiguous array segment whose sum is at most a limit. Every value must be nonnegative.

What stays true

After shrinking, sum equals the total in [left, right] and is at most the limit. Removing another left value cannot produce a longer valid segment ending here.

Time
O(n)
Extra space
O(1)
sliding_window.py
def longest_window(nums: list[int], limit: int) -> int:
    """Longest segment with sum <= limit; nums must be nonnegative."""
    if limit < 0:
        return 0
    left = total = best = 0
    for right, value in enumerate(nums):
        total += value
        while total > limit:
            total -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

Functions and classes only. Call them from your judge’s required entry point.

nums = [2, 1, 3, 1], limit = 4 → 2. Both [2, 1] and [3, 1] have length 2.

Keep the sum at most 4

Extend

  1. 2 (active)
  2. 1 (active)
  3. 3
  4. 1

[2, 1] sums to 3 and has length 2.

1 / 4