# 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.

```java
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.

```java
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.

```java
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.

```java
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.

```java
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).