2 Pointers - Sliding window - Templates

A sliding window keeps track of a continuous part of an array or string. The pointers l and r mark its boundaries; its length is r - l + 1.

Pattern 1 - Fixed-size window

Example: Find the maximum subarray sum for a fixed length k.

Calculate the first window's sum. Then remove the leftmost element, add the next element on the right, and update the maximum.

Assume 1 <= k <= arr.length. Negative elements are allowed.

private static long findMaxSum(int[] arr, int k) {
    int l = 0;
    int r = k - 1;
    long windowSum = initialWindowSum(arr, k);
    long maxSum = windowSum;

    while (r < arr.length - 1) {
        windowSum -= arr[l];
        l++;
        r++;
        windowSum += arr[r];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

private static long initialWindowSum(int[] arr, int k) {
    long sum = 0;
    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }
    return sum;
}

For [-1, 2, 3, 3, 4, 5, -1] and k = 4, the answer is 15 from [3, 3, 4, 5].

Time: O(n). Extra space: O(1).

Pattern 2 - Longest window satisfying a condition

Example: Find the longest subarray with sum <= maxSum.

For [2, 5, 1, 7, 10] and maxSum = 14, the answer is 3. Both [2, 5, 1] and [5, 1, 7] qualify.

The sliding-window versions below assume nonnegative elements and a nonnegative limit. Adding cannot decrease the sum; removing cannot increase it. Negative elements break this reasoning. Use long for sums to avoid integer overflow.

Brute force

Try every starting index and extend the subarray to every ending index.

private static int longestAtMostBruteForce(int maxSum, int[] arr) {
    int maxLength = 0;

    for (int l = 0; l < arr.length; l++) {
        long currentSum = 0;
        for (int r = l; r < arr.length; r++) {
            currentSum += arr[r];
            if (currentSum <= maxSum) {
                maxLength = Math.max(maxLength, r - l + 1);
            }
        }
    }

    return maxLength;
}

Time: O(n²). Extra space: O(1).

Sliding window - shrink → add → check and update

Fix an oversized window from the previous iteration, add the next element, and measure only if valid. If adding makes it invalid, shrinking waits until the next iteration.

private static int longestAtMostShrinkFirst(int maxSum, int[] arr) {
    int maxLength = 0;
    int l = 0;
    int r = 0;
    long currentSum = 0;

    while (r < arr.length) {
        // 1. SHRINK: fix the previous window.
        while (currentSum > maxSum) {
            currentSum -= arr[l];
            l++;
        }

        // 2. ADD: include the next element.
        currentSum += arr[r];

        // 3. CHECK AND UPDATE: measure only if valid.
        if (currentSum <= maxSum) {
            maxLength = Math.max(maxLength, r - l + 1);
        }
        r++;
    }

    return maxLength;
}

Sliding window - add → shrink → update

Grow the window, shrink until its sum is within the limit, then measure it. The window is valid before updating the answer.

private static int findLongestSubarrayWithSumAtMost(
        int maxSum, int[] arr) {

    int maxLength = 0;
    int l = 0;
    long currentSum = 0;

    for (int r = 0; r < arr.length; r++) {
        // 1. ADD: include the next element.
        currentSum += arr[r];

        // 2. SHRINK: restore a valid window.
        while (currentSum > maxSum) {
            currentSum -= arr[l];
            l++;
        }

        // 3. UPDATE: measure the valid window.
        maxLength = Math.max(maxLength, r - l + 1);
    }

    return maxLength;
}

Both versions take O(n) time and O(1) extra space. Each element enters and leaves the window at most once, even with the inner while loop.

Single-shrink alternative

Remove at most one element per iteration. The window may remain invalid, so update the answer only when valid. Its length never decreases: each iteration adds one element and removes at most one. This is enough to find a longer valid window.

private static int longestAtMostSingleShrink(int maxSum, int[] arr) {
    int maxLength = 0;
    int l = 0;
    int r = 0;
    long currentSum = 0;

    while (r < arr.length) {
        // Remove one element if the previous window was invalid.
        if (currentSum > maxSum) {
            currentSum -= arr[l];
            l++;
        }

        currentSum += arr[r];

        // The window may still be invalid.
        if (currentSum <= maxSum) {
            maxLength = Math.max(maxLength, r - l + 1);
        }
        r++;
    }

    return maxLength;
}

Time: O(n). Extra space: O(1). This has the same time complexity as the two versions above; use it for the longest length, not for counting all valid subarrays.

Pattern 3 - Count subarrays satisfying a condition

Example: Count subarrays with sum exactly k in a nonnegative integer array.

countExactly(k) = countAtMost(k) - countAtMost(k - 1)

To calculate countAtMost(limit), use add → shrink → count. After shrinking to a valid window, add r - l + 1 to the count: every subarray ending at r and starting between l and r is valid.

Return 0 for a negative limit, and use a long count because there can be n * (n + 1) / 2 subarrays.

Time: O(n) for the two passes. Extra space: O(1).

Pattern 4 - Shortest window satisfying a condition

Example: Find the shortest subarray with sum at least a positive target in a nonnegative array.

Use add → update and shrink while valid:

1. Add the next element on the right.
2. While the sum meets the target, record the minimum length and remove the leftmost element.
3. Continue expanding when the window becomes invalid.

For the longest-window pattern, shrink while invalid. For the shortest-window pattern, measure and shrink while valid.

Time: O(n). Extra space: O(1).