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.cpp
#include <algorithm>
#include <array>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
using namespace std;

int longestWindow(const vector<long long>& nums, long long limit) {
    if (limit < 0) return 0;
    int left = 0, best = 0;
    long long total = 0;
    for (int right = 0; right < (int)nums.size(); ++right) {
        total += nums[right];
        while (total > limit) total -= nums[left++];
        best = max(best, right - left + 1);
    }
    return best;
}

Functions and structures only. Add the judge’s required entry point and input/output handling.

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