PK

PKBytes

Explore tracks
Chapter 7: Foundational Problem-Solving Patterns
7.04Beginner5 topics22 min5 interactive animations

Sliding windows

A sliding window keeps a contiguous range [left, right] and updates its state incrementally as the edges move. Fixed windows slide one step at a time; variable windows grow on the right and shrink on the left.

Learning goals

  • Slide a fixed-size window in O(n) instead of O(n · k)
  • Grow and shrink a variable window while it stays valid
  • Count subarrays with “at most K” and derive “exactly K” by subtraction
  • Find the smallest window that covers a requirement

Prerequisites

Two pointersFrequency mapsPrefix sums (for comparison)

To find your busiest hour of website traffic minute by minute, you do not re-add sixty numbers for each hour. You add the newest minute and subtract the oldest.

7.04.1

Fixed-size windows

For windows of exactly k elements, compute the first window, then for each step add the entering element and remove the leaving one. Each step is O(1), so the whole scan is O(n) no matter how large k is.

The window state can be anything that supports add and remove: a sum, a frequency map, or a count of vowels.

Worst

O(n)

Space

O(1)

Fixed-size window: maximum sum of k consecutive values

Interactive · edit the input

Your input

Try

int[] arr · length 9

2
1
5
1
3
2
7
1
4
012345678
EnteringLeavingBest window
Setup

The first window [0..2] sums to 8. That costs k additions, once.

Step 1 / 8
Java
1public static int maxWindowSum(int[] arr, int k) {
2    int sum = 0;
3    for (int i = 0; i < k; i++) sum += arr[i];        // first window
4    int best = sum;
5    for (int right = k; right < arr.length; right++) {
6        sum += arr[right] - arr[right - k];          // add the new value, drop the old one
7        best = Math.max(best, sum);
8    }
9    return best;
10}

Live state

3 additions

k

3

sum

8

best

8

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L3k=3 sum=8 best=8The first window [0..2] sums to 8. That costs k additions, once.
2L6k=3 sum=7 best=8Slide right: + arr[3] (1) − arr[0] (2) = 7. Two operations instead of re-adding k values.
3L6k=3 sum=9 best=9Slide right: + arr[4] (3) − arr[1] (1) = 9. Two operations instead of re-adding k values. New best.
4L6k=3 sum=6 best=9Slide right: + arr[5] (2) − arr[2] (5) = 6. Two operations instead of re-adding k values.
5L6k=3 sum=12 best=12Slide right: + arr[6] (7) − arr[3] (1) = 12. Two operations instead of re-adding k values. New best.
6L6k=3 sum=10 best=12Slide right: + arr[7] (1) − arr[4] (3) = 10. Two operations instead of re-adding k values.
7L6k=3 sum=12 best=12Slide right: + arr[8] (4) − arr[5] (2) = 12. Two operations instead of re-adding k values.
8L9return=12return 12, from window [4..6]. O(n) time instead of O(n · k).
7.04.2

Variable-size windows

A variable window grows by moving right and shrinks by moving left. It works when the condition is monotonic: adding an element can only push the window toward invalid (or toward valid), and removing one moves it the other way. Positive numbers and sum constraints have this property.

Each index enters the window once and leaves at most once, so even with a while loop inside the for loop the total work is O(n).

Variable window: shortest subarray with sum ≥ target

Interactive · edit the input

Your input

Try

int[] arr · length 6

2
3
1
2
4
3
012345
EnteringLeavingBest window
Setup

Positive values make the window sum grow when right moves and shrink when left moves. That monotonicity is what lets a window work.

Step 1 / 18
Java
1public static int minSubArrayLen(int target, int[] arr) {   // all values positive
2    int left = 0, sum = 0, best = Integer.MAX_VALUE;
3    for (int right = 0; right < arr.length; right++) {
4        sum += arr[right];                          // grow the window
5        while (sum >= target) {                     // valid: try to shrink it
6            best = Math.min(best, right - left + 1);
7            sum -= arr[left++];
8        }
9    }
10    return best == Integer.MAX_VALUE ? 0 : best;
11}

Live state

0 pointer moves

target

7

left

0

sum

0

best

∞

No condition evaluated on this step
Execution trace (dry run table)Show 18 steps
StepLineStateWhat happens
1L2target=7 left=0 sum=0 best=∞Positive values make the window sum grow when right moves and shrink when left moves. That monotonicity is what lets a window work.
2L4target=7 left=0 right=0 sum=2 best=∞Add arr[0] = 2; window sum is 2.
3L4target=7 left=0 right=1 sum=5 best=∞Add arr[1] = 3; window sum is 5.
4L4target=7 left=0 right=2 sum=6 best=∞Add arr[2] = 1; window sum is 6.
5L4target=7 left=0 right=3 sum=8 best=∞Add arr[3] = 2; window sum is 8.
6L6target=7 left=0 right=3 sum=8 best=4[0..3] reaches the target with length 4. Best so far: 4. Now try a shorter window.
7L7target=7 left=1 right=3 sum=6 best=4Drop arr[0]; sum is 6.
8L4target=7 left=1 right=4 sum=10 best=4Add arr[4] = 4; window sum is 10.
9L6target=7 left=1 right=4 sum=10 best=4[1..4] reaches the target with length 4. Best so far: 4. Now try a shorter window.
10L7target=7 left=2 right=4 sum=7 best=4Drop arr[1]; sum is 7.
11L6target=7 left=2 right=4 sum=7 best=3[2..4] reaches the target with length 3. Best so far: 3. Now try a shorter window.
12L7target=7 left=3 right=4 sum=6 best=3Drop arr[2]; sum is 6.
13L4target=7 left=3 right=5 sum=9 best=3Add arr[5] = 3; window sum is 9.
14L6target=7 left=3 right=5 sum=9 best=3[3..5] reaches the target with length 3. Best so far: 3. Now try a shorter window.
15L7target=7 left=4 right=5 sum=7 best=3Drop arr[3]; sum is 7.
16L6target=7 left=4 right=5 sum=7 best=2[4..5] reaches the target with length 2. Best so far: 2. Now try a shorter window.
17L7target=7 left=5 right=5 sum=3 best=2Drop arr[4]; sum is 3.
18L10return=2return 2. Each index entered and left the window at most once: 11 pointer moves, O(n).
7.04.3

At-most-K constraints

For “at most K distinct values” or “at most K zeros”, keep counts inside the window. When the window breaks the limit, shrink from the left until it is valid again, then record the answer for this right.

Shrinking is safe because any window that contains the invalid one is also invalid, so no answer is skipped.

At most K distinct: longest valid window

Interactive · edit the input

Your input

Try

int[] arr · length 8

1
2
1
2
3
2
2
4
01234567
EnteringLeavingCurrent valid window
Setup

The map counts each value inside the window; its size is the number of distinct values.

Step 1 / 23
Java
1public static int longestAtMostK(int[] arr, int k) {
2    Map<Integer, Integer> count = new HashMap<>();
3    int left = 0, best = 0;
4    for (int right = 0; right < arr.length; right++) {
5        count.merge(arr[right], 1, Integer::sum);
6        while (count.size() > k) {                    // too many distinct values
7            if (count.merge(arr[left], -1, Integer::sum) == 0) count.remove(arr[left]);
8            left++;
9        }
10        best = Math.max(best, right - left + 1);
11    }
12    return best;
13}

Live state

k

2

No condition evaluated on this step
Execution trace (dry run table)Show 23 steps
StepLineStateWhat happens
1L2k=2The map counts each value inside the window; its size is the number of distinct values.
2L5k=2 left=0 right=0 distinct=1 best=0Add 1. The window has 1 distinct value.
3L10k=2 left=0 right=0 best=1[0..0] is valid with length 1. Best is 1.
4L5k=2 left=0 right=1 distinct=2 best=1Add 2. The window has 2 distinct values.
5L10k=2 left=0 right=1 best=2[0..1] is valid with length 2. Best is 2.
6L5k=2 left=0 right=2 distinct=2 best=2Add 1. The window has 2 distinct values.
7L10k=2 left=0 right=2 best=3[0..2] is valid with length 3. Best is 3.
8L5k=2 left=0 right=3 distinct=2 best=3Add 2. The window has 2 distinct values.
9L10k=2 left=0 right=3 best=4[0..3] is valid with length 4. Best is 4.
10L5k=2 left=0 right=4 distinct=3 best=4Add 3. The window has 3 distinct values.
11L7k=2 left=1 right=4 distinct=3Too many distinct values: drop 1 from the left.
12L7k=2 left=2 right=4 distinct=3Too many distinct values: drop 2 from the left.
13L7k=2 left=3 right=4 distinct=2Too many distinct values: drop 1 from the left, which removes 1 from the window entirely.
14L10k=2 left=3 right=4 best=4[3..4] is valid with length 2. Best is 4.
15L5k=2 left=3 right=5 distinct=2 best=4Add 2. The window has 2 distinct values.
16L10k=2 left=3 right=5 best=4[3..5] is valid with length 3. Best is 4.
17L5k=2 left=3 right=6 distinct=2 best=4Add 2. The window has 2 distinct values.
18L10k=2 left=3 right=6 best=4[3..6] is valid with length 4. Best is 4.
19L5k=2 left=3 right=7 distinct=3 best=4Add 4. The window has 3 distinct values.
20L7k=2 left=4 right=7 distinct=3Too many distinct values: drop 2 from the left.
21L7k=2 left=5 right=7 distinct=2Too many distinct values: drop 3 from the left, which removes 3 from the window entirely.
22L10k=2 left=5 right=7 best=4[5..7] is valid with length 3. Best is 4.
23L12return=4return 4, window [0..3]. Each index enters and leaves once: O(n).
7.04.4

Exact-K via subtraction

“Exactly K” is not monotonic: a window with exactly K distinct values may grow into one with K + 1, then shrink back to K. A single window cannot track that cleanly.

Instead count windows with at most K and subtract those with at most K − 1. For each right, the number of valid subarrays ending there is right - left + 1, so each count is a single O(n) pass.

Exactly K distinct = atMost(K) − atMost(K − 1)

Interactive · edit the input

Your input

Try

int[] arr · length 5

1
2
1
2
3
01234
EnteringLeavingValid window
Setup

Counting “exactly 2” directly is awkward for a window, because shrinking can skip past valid states. Count “at most 2” and subtract “at most 1”.

Step 1 / 32
Java
1public static int exactlyK(int[] arr, int k) {
2    return atMost(arr, k) - atMost(arr, k - 1);
3}
4
5static int atMost(int[] arr, int k) {
6    Map<Integer, Integer> count = new HashMap<>();
7    int left = 0, total = 0;
8    for (int right = 0; right < arr.length; right++) {
9        count.merge(arr[right], 1, Integer::sum);
10        while (count.size() > k) {
11            if (count.merge(arr[left], -1, Integer::sum) == 0) count.remove(arr[left]);
12            left++;
13        }
14        total += right - left + 1;                 // subarrays ending at right
15    }
16    return total;
17}

Live state

k

2

No condition evaluated on this step
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L2k=2Counting “exactly 2” directly is awkward for a window, because shrinking can skip past valid states. Count “at most 2” and subtract “at most 1”.
2L5k=2Pass 1: atMost(arr, 2).
3L9k=2 left=0 right=0 distinct=1 total=0Add 1. The window has 1 distinct value.
4L14k=2 left=0 right=0 total=1Every subarray ending at 0 and starting in [0..0] is valid: 1 subarray. Total 1.
5L9k=2 left=0 right=1 distinct=2 total=1Add 2. The window has 2 distinct values.
6L14k=2 left=0 right=1 total=3Every subarray ending at 1 and starting in [0..1] is valid: 2 subarrays. Total 3.
7L9k=2 left=0 right=2 distinct=2 total=3Add 1. The window has 2 distinct values.
8L14k=2 left=0 right=2 total=6Every subarray ending at 2 and starting in [0..2] is valid: 3 subarrays. Total 6.
9L9k=2 left=0 right=3 distinct=2 total=6Add 2. The window has 2 distinct values.
10L14k=2 left=0 right=3 total=10Every subarray ending at 3 and starting in [0..3] is valid: 4 subarrays. Total 10.
11L9k=2 left=0 right=4 distinct=3 total=10Add 3. The window has 3 distinct values.
12L11k=2 left=1 right=4 distinct=3Too many distinct values: drop 1 from the left.
13L11k=2 left=2 right=4 distinct=3Too many distinct values: drop 2 from the left.
14L11k=2 left=3 right=4 distinct=2Too many distinct values: drop 1 from the left, which removes 1 from the window entirely.
15L14k=2 left=3 right=4 total=12Every subarray ending at 4 and starting in [3..4] is valid: 2 subarrays. Total 12.
16L16atMost(2)=12atMost(2) = 12.
17L5k=1 atMost(2)=12Pass 2: atMost(arr, 1).
18L9k=1 left=0 right=0 distinct=1 total=0Add 1. The window has 1 distinct value.
19L14k=1 left=0 right=0 total=1Every subarray ending at 0 and starting in [0..0] is valid: 1 subarray. Total 1.
20L9k=1 left=0 right=1 distinct=2 total=1Add 2. The window has 2 distinct values.
21L11k=1 left=1 right=1 distinct=1Too many distinct values: drop 1 from the left, which removes 1 from the window entirely.
22L14k=1 left=1 right=1 total=2Every subarray ending at 1 and starting in [1..1] is valid: 1 subarray. Total 2.
23L9k=1 left=1 right=2 distinct=2 total=2Add 1. The window has 2 distinct values.
24L11k=1 left=2 right=2 distinct=1Too many distinct values: drop 2 from the left, which removes 2 from the window entirely.
25L14k=1 left=2 right=2 total=3Every subarray ending at 2 and starting in [2..2] is valid: 1 subarray. Total 3.
26L9k=1 left=2 right=3 distinct=2 total=3Add 2. The window has 2 distinct values.
27L11k=1 left=3 right=3 distinct=1Too many distinct values: drop 1 from the left, which removes 1 from the window entirely.
28L14k=1 left=3 right=3 total=4Every subarray ending at 3 and starting in [3..3] is valid: 1 subarray. Total 4.
29L9k=1 left=3 right=4 distinct=2 total=4Add 3. The window has 2 distinct values.
30L11k=1 left=4 right=4 distinct=1Too many distinct values: drop 2 from the left, which removes 2 from the window entirely.
31L14k=1 left=4 right=4 total=5Every subarray ending at 4 and starting in [4..4] is valid: 1 subarray. Total 5.
32L2atMost(2)=12 atMost(1)=5 return=7return 12 − 5 = 7 subarrays with exactly 2 distinct values. Two O(n) passes.
7.04.5

Minimum covering window

Minimum window problems (shortest substring containing all required characters) expand right until the window covers the requirement, then shrink left while it still covers it, recording the best length each time.

Track how many requirements are satisfied, not just the counts, so checking “is the window valid?” stays O(1). The animation finds the shortest window containing every distinct value of the array.

Java
1static String minWindow(String s, String t) {
2    int[] need = new int[128];
3    for (char c : t.toCharArray()) need[c]++;
4    int missing = t.length(), left = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
5    for (int right = 0; right < s.length(); right++) {
6        if (need[s.charAt(right)]-- > 0) missing--;           // this char was still required
7        while (missing == 0) {
8            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; }
9            if (++need[s.charAt(left++)] > 0) missing++;      // removing it breaks coverage
10        }
11    }
12    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
13}

Worst

O(n + m)

Space

O(alphabet)

Minimum window covering every distinct value

Interactive · edit the input

Your input

Try

int[] arr · length 8

2
1
1
3
2
1
1
3
01234567
EnteringLeavingCovering window
Setup

The array contains 3 distinct values. Find the shortest window containing all of them.

Step 1 / 20
Java
1public static int[] minWindowAllDistinct(int[] arr) {
2    int need = (int) Arrays.stream(arr).distinct().count();
3    Map<Integer, Integer> count = new HashMap<>();
4    int left = 0, bestLen = Integer.MAX_VALUE, bestL = 0;
5    for (int right = 0; right < arr.length; right++) {
6        count.merge(arr[right], 1, Integer::sum);
7        while (count.size() == need) {                // window covers every value
8            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; }
9            if (count.merge(arr[left], -1, Integer::sum) == 0) count.remove(arr[left]);
10            left++;
11        }
12    }
13    return new int[] { bestL, bestL + bestLen - 1 };
14}

Live state

need

3

No condition evaluated on this step
Execution trace (dry run table)Show 20 steps
StepLineStateWhat happens
1L2need=3The array contains 3 distinct values. Find the shortest window containing all of them.
2L6need=3 have=1 best=∞Add 2. The window has 1 of 3 values.
3L6need=3 have=2 best=∞Add 1. The window has 2 of 3 values.
4L6need=3 have=2 best=∞Add 1. The window has 2 of 3 values.
5L6need=3 have=3 best=∞Add 3. The window has 3 of 3 values.
6L8need=3 have=3 best=4[0..3] covers everything (length 4). Shrink from the left to look for a shorter one.
7L10need=3 have=2 best=4Dropping 2 loses the last copy of 2: the window no longer covers everything.
8L6need=3 have=3 best=4Add 2. The window has 3 of 3 values.
9L8need=3 have=3 best=4[1..4] covers everything (length 4). Shrink from the left to look for a shorter one.
10L10need=3 have=3 best=4Drop 1; another copy is still inside.
11L8need=3 have=3 best=3[2..4] covers everything (length 3). Shrink from the left to look for a shorter one.
12L10need=3 have=2 best=3Dropping 1 loses the last copy of 1: the window no longer covers everything.
13L6need=3 have=3 best=3Add 1. The window has 3 of 3 values.
14L8need=3 have=3 best=3[3..5] covers everything (length 3). Shrink from the left to look for a shorter one.
15L10need=3 have=2 best=3Dropping 3 loses the last copy of 3: the window no longer covers everything.
16L6need=3 have=2 best=3Add 1. The window has 2 of 3 values.
17L6need=3 have=3 best=3Add 3. The window has 3 of 3 values.
18L8need=3 have=3 best=3[4..7] covers everything (length 4). Shrink from the left to look for a shorter one.
19L10need=3 have=2 best=3Dropping 2 loses the last copy of 2: the window no longer covers everything.
20L13return=[2, 4]Shortest covering window is [2..4] (length 3). O(n) with a map.

Practice ladder

Now try it yourself

Easy

  • Maximum average subarray I
  • Contains duplicate II (window of size k)

Medium

  • Longest substring without repeating characters
  • Minimum size subarray sum
  • Longest repeating character replacement
  • Permutation in string

Advanced

  • Minimum window substring
  • Subarrays with K different integers
  • Sliding window median

Key takeaways

  • Fixed windows add one element and remove one per step: O(n).
  • Variable windows need a monotonic condition; each index enters and leaves at most once.
  • Exactly K = atMost(K) − atMost(K − 1); covering windows expand until valid, then shrink.