# LU.2 Sliding Window

> Keep a running answer for a contiguous range, adding the item that enters and removing the one that leaves, instead of recomputing every window.

Chapter: Level Up: Problem Patterns · ~45 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/sliding-window

## Mental model

A **train window**: as the train moves, one new tree appears on the right and one old tree disappears on the left. You don't need to look at the whole view again.

### Fixed window (size k)

Compute the first window's sum once. Then for each step: `sum += a[r] − a[r − k]`. That is **O(n)** instead of O(n·k).

### Variable window

Two pointers `l` and `r` mark the window. Move `r` to **grow** it. Whenever the window breaks a rule (a repeated letter, a sum too big), move `l` to **shrink** it until it is valid again. Each index enters once and leaves once, so the total is **O(n)**, even with the inner `while`.

> Built on arrays (Ch1) and two pointers. Not on the exam.

## C++ code: sliding-window.cpp

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int maxSum(const vector<int>& a, int k) {             // fixed-size window
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int r = k; r < (int)a.size(); r++) {
        sum += a[r] - a[r - k];                        // add new, drop old
        best = max(best, sum);
    }
    return best;
}

int longestUnique(const string& s) {                  // variable-size window
    int seen[256] = {};
    int best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); r++) {
        seen[(unsigned char)s[r]]++;
        while (seen[(unsigned char)s[r]] > 1) seen[(unsigned char)s[l++]]--;   // shrink until valid
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    cout << "max sum of 3: " << maxSum({2, 1, 5, 1, 3, 2, 7, 1}, 3) << "\n";
    cout << "longest without repeats in \"abcabcbb\": " << longestUnique("abcabcbb") << "\n";
}
```

Expected output:

```text
max sum of 3: 12
longest without repeats in "abcabcbb": 3
```

## Complexity

| Case | Cost |
| --- | --- |
| recompute every window | O(n·k) |
| fixed sliding window | O(n) |
| variable window (grow/shrink) | O(n): each item enters and leaves once |

Space: O(1), or O(alphabet) for a frequency table

Sliding windows work on **contiguous** ranges (subarrays, substrings), not subsequences.

## Videos

- [Sliding Window in 7 minutes](https://youtu.be/y2d0VHdvfdc) (AlgoMasterIO): Fixed vs variable windows in 7 minutes.
- [Sliding Window: Best Time to Buy and Sell Stock](https://youtu.be/1pkOgXD63yU) (NeetCode): NeetCode applies the window idea to Best Time to Buy and Sell Stock.

## Exam lens

Likely questions:

- What is the difference between a fixed and a variable sliding window?
- Why is the variable window still O(n) even though it has a nested while loop?

Common mistakes:

- Off-by-one when dropping the old item. It is `a[r − k]`, not `a[r − k + 1]`.
- Using a window on a problem that asks for a subsequence (not contiguous).
- Forgetting to update the answer after shrinking.

## Quick check

1. `2 1 5 1 3 2`, k = 3. The window sums are…
   A. 8, 7, 9, 6
   B. 8, 7, 9, 6, 5
   C. 3, 6, 6, 4
   D. 8, 9
   Answer: A. 2+1+5, 1+5+1, 5+1+3, 1+3+2.

2. Moving the window right by one costs…
   A. O(k)
   B. O(1)
   C. O(n)
   D. O(log n)
   Answer: B. Add the new item, subtract the old one.

3. Longest substring without repeats in `pwwkew`?
   A. 2
   B. 3
   C. 4
   D. 6
   Answer: B. `wke`.

## Practice

**Trace by hand.** Max sum of k = 3 in `2 1 5 1 3 2 7 1`. List each window sum.

Solution:

8, 7, 9, 6, 12, 10 → best **12** (`3 2 7`).

**Implement it.** Find the length of the shortest subarray with sum ≥ S (all numbers positive).

Hint: Grow `r`, adding to sum. While `sum >= S`, record `r − l + 1` and shrink from the left.

**Problems:**

- [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) (easy). Hint: Track the lowest price so far; the window is "buy day … today".
- [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/) (medium). Hint: This page's `longestUnique()`.
- [Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/) (medium). Hint: Variable window. Shrink while the sum is big enough.

## Mastery checklist

- [ ] I can write a fixed-size window in O(n).
- [ ] I can write a variable window that grows and shrinks.
- [ ] I can explain why both are O(n).