Sliding window

A sliding window maintains a contiguous subarray/substring with two indices—expand right to grow, shrink left when constraint breaks. Ideal for max sum of length k or longest substring with at most k distinct chars.

Fixed window size k

Add new element at right, subtract leaving element at left—O(n) total.

Max sum of size 3

#include 
#include 

int main() {
    std::vector a = {2, 1, 5, 1, 3, 2};
    int k = 3, window = 0, best = 0;
    for (int i = 0; i < (int)a.size(); ++i) {
        window += a[i];
        if (i >= k) window -= a[i - k];
        if (i >= k - 1) best = std::max(best, window);
    }
    std::cout << "max sum k=3: " << best << "\n";
    return 0;
}

Variable window

Move left until valid (e.g. sum ≤ target), track best while valid—common in string problems.

Important interview questions and answers

1. Q: Sliding window vs nested loops?
   A: Window moves each index once—O(n) vs O(n·k) or O(n²).
2. Q: Fixed vs variable?
   A: Fixed k uses constant-size window; variable adjusts left based on constraint.

Self-check

1. What is complexity of fixed-size sliding window on array length n?
2. When do you subtract a[i-k] from the window?

Tip: Fixed window: add right, subtract left when i >= k.