<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. DSA
  3. Hashing and problem-solving techniques
All lessons in this course

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Lesson 22 of 50 14 minIntermediate

Sliding window

Solve “best run of consecutive items” problems in O(n) by updating a window as it moves: fixed-size windows, growing and shrinking windows, and windows with a dictionary.

Many questions are about consecutive items: the busiest 3 days, the longest stretch under a weight limit, the longest piece of text without a repeated letter. The slow way recomputes every possible stretch from scratch. A sliding window keeps one stretch (the window) and updates it as it moves: add what enters on the right, remove what leaves on the left.

Fixed-size window

Steel deliveries per day are { 4, 2, 7, 1, 8, 3, 5, 6, 2, 9 } tonnes. Which 3 consecutive days were the busiest? Adding up each 3-day window separately does k additions per window: O(n·k). But two neighbouring windows share all but one day, so moving the window needs only one addition and one subtraction.

Interactive

A sliding window

Steel delivered per day (tonnes). The window is a run of consecutive days. When it moves, update the sum with what enters and what leaves. Never re-add the whole window.

k
40
21
72
13
84
35
56
67
28
99

Purple = current window · green underline = best window so far

Window sum 4 · Best sum 0 · Steps 1
Build the first window: add day 0 (4). Sum = 4.
FixedWindow.cs
static (int best, int start) MaxWindowSum(int[] a, int k){    int sum = 0;    for (int i = 0; i < k; i++) sum += a[i];       // the first window    int best = sum, start = 0;    for (int r = k; r < a.Length; r++)    {        sum += a[r] - a[r - k];                     // add the new day, drop the oldest        if (sum > best) { best = sum; start = r - k + 1; }    }    return (best, start);} int[] loads = { 4, 2, 7, 1, 8, 3, 5, 6, 2, 9 };var (most, firstDay) = MaxWindowSum(loads, 3);Console.WriteLine($"Busiest 3 days: {most} t, starting day {firstDay}");
Output
Busiest 3 days: 17 t, starting day 7

The same idea gives moving averages (divide the window sum by k), the number of defects in every 100 consecutive welds, and so on. Anything you can add and remove in O(1) can live in a window.

Variable-size window: grow and shrink

Now the question is “what is the longest run of days whose total stays within 12 t?”. The window size is not fixed. The rule:

  1. Move right one step and add that item (grow).
  2. While the window breaks the rule (sum > limit), remove the item at left and move left forward (shrink).
  3. The window is now valid. Record it if it is the best so far.
GrowShrink.cs
static (int length, int start) LongestWithin(int[] a, int limit){    int left = 0, sum = 0, bestLen = 0, bestStart = 0;    for (int right = 0; right < a.Length; right++)    {        sum += a[right];                    // grow on the right        while (sum > limit)                 // too much: shrink from the left            sum -= a[left++];        if (right - left + 1 > bestLen) { bestLen = right - left + 1; bestStart = left; }    }    return (bestLen, bestStart);} int[] loads = { 4, 2, 7, 1, 8, 3, 5, 6, 2, 9 };var (days, startDay) = LongestWithin(loads, 12);Console.WriteLine($"Longest run within 12 t: {days} days from day {startDay}");
Output
Longest run within 12 t: 3 days from day 1

It looks like a loop inside a loop, but it is O(n): right moves n times and left moves at most n times in total, because it never goes back. Count the total moves of each pointer, not the nesting of the loops.

A window with a dictionary

The window can hold more than a sum. Here it tracks which characters are inside, to find the longest piece of text with no repeated character. A dictionary remembers where each character was last seen, so left can jump straight past the earlier copy.

LongestUnique.cs
static int LongestUnique(string s){    var lastSeen = new Dictionary<char, int>();    int left = 0, best = 0;    for (int right = 0; right < s.Length; right++)    {        if (lastSeen.TryGetValue(s[right], out int prev) && prev >= left)            left = prev + 1;                 // jump past the earlier copy        lastSeen[s[right]] = right;        best = Math.Max(best, right - left + 1);    }    return best;} Console.WriteLine(LongestUnique("abcabcbb"));   // "abc"Console.WriteLine(LongestUnique("pwwkew"));     // "wke"
Output
3
3
Problem says…Window
“every k consecutive…”, moving averageFixed size k
“longest run such that…”Grow, and shrink while the rule is broken; record after shrinking
“shortest run such that…”Grow until the rule holds, then shrink while it still holds, recording each time
Rule about distinct or repeated itemsWindow plus a HashSet or Dictionary of counts
Quick check

The grow-and-shrink code has a while loop inside a for loop. Why is it O(n) and not O(n²)?

Quick check

Window size k = 4, the window sum is 20. The item entering is 7 and the item leaving is 3. New sum?

Practice

Write MinLengthAtLeast(int[] a, int target) that returns the length of the shortest run of consecutive positive numbers whose sum is at least target, or 0 if there is none. { 2, 3, 1, 2, 4, 3 } with target 7 → 2 (the run 4, 3). { 1, 1, 1 } with target 5 → 0.

Show a hint

Grow on the right. While the sum is at least the target, record the length and shrink from the left: you are looking for the smallest window that still works.

Show the solution
Solution.cs
static int MinLengthAtLeast(int[] a, int target){    int left = 0, sum = 0, best = int.MaxValue;    for (int right = 0; right < a.Length; right++)    {        sum += a[right];        while (sum >= target)                  // valid: try to make it shorter        {            best = Math.Min(best, right - left + 1);            sum -= a[left++];        }    }    return best == int.MaxValue ? 0 : best;} Console.WriteLine(MinLengthAtLeast(new[] { 2, 3, 1, 2, 4, 3 }, 7));Console.WriteLine(MinLengthAtLeast(new[] { 1, 1, 1 }, 5));
Output
2
0

Remember

  • A sliding window updates a run of consecutive items with what enters and leaves, instead of recomputing it.
  • Fixed-size windows cost one add and one remove per step: O(n) instead of O(n·k).
  • Variable windows grow on the right and shrink on the left; both pointers only move forward, so it is O(n).
  • Grow-and-shrink on sums needs non-negative values; a dictionary inside the window handles “distinct” rules.
0 of 50 lessons completed