Sliding Window Basics

A sliding window is a subarray that moves through the array. As the window shifts, you update the answer efficiently instead of recalculating from scratch each time.

Fixed-Size Window

Given an array and a window size K, find the maximum sum of any K consecutive elements. Slide the window by subtracting the element that left and adding the one that entered.

Problem: Max sum of K consecutive elements

Given N, K, and an array, find the maximum sum of any subarray of length K.

Sample input:
6 3
2 5 1 8 3 4

Expected output:
12  (subarray 1+8+3 or 8+3+4)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // first window
    int window = 0;
    for (int i = 0; i < k; i++) window += arr[i];
    int best = window;

    // slide
    for (int i = k; i < n; i++) {
        window += arr[i] - arr[i - k];
        best = max(best, window);
    }
    cout << best << "\n";
    return 0;
}

Rust

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().lock().read_to_string(&mut input).unwrap();
    let nums: Vec<i64> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let n = nums[0] as usize;
    let k = nums[1] as usize;
    let arr = &nums[2..2 + n];

    let mut window: i64 = arr[..k].iter().sum();
    let mut best = window;
    for i in k..n {
        window += arr[i] - arr[i - k];
        best = best.max(window);
    }
    println!("{}", best);
}

💡 O(N) instead of O(N·K)

Without the sliding window, you'd sum K elements for each of N positions — O(N·K). With the sliding window, each step is O(1), giving O(N) total.

Variable-Size Window

Sometimes the window size isn't fixed — it grows or shrinks based on a condition. The right pointer extends the window; the left pointer shrinks it when the condition is violated.

Problem: Longest subarray with sum ≤ S

Find the longest contiguous subarray whose sum is at most S.

Sample input:
7 10
3 2 5 1 8 2 4

Expected output:
3  (subarray 2+5+1=8 ≤ 10, length 3)

C++

int left = 0, sum = 0, best = 0;
for (int right = 0; right < n; right++) {
    sum += arr[right];
    while (sum > S) {
        sum -= arr[left];
        left++;
    }
    best = max(best, right - left + 1);
}
cout << best << "\n";

Rust

let mut left = 0;
let mut sum = 0;
let mut best = 0;
for right in 0..n {
    sum += arr[right];
    while sum > S {
        sum -= arr[left];
        left += 1;
    }
    best = best.max(right - left + 1);
}
println!("{}", best);

Key Takeaways

→ Fixed window: add the new element, subtract the old one — O(N).
→ Variable window: grow with right, shrink with left.
→ Sliding window saves recomputing sums/counts from scratch.

Fixed-Size Window

Problem: Max sum of K consecutive elements

C++

Rust

Variable-Size Window

Problem: Longest subarray with sum ≤ S

C++

Rust

Key Takeaways

Practice