Chapter 22 of 65

Sliding Window Technique

Imagine you are on a train, looking out through a window. As the train moves, a new tree appears on one side of the window and an old tree disappears from the other side. You never have to look at the whole landscape again. You only notice what enters and what leaves.

That is exactly the idea behind the Sliding Window Technique.

Many interview problems ask about a contiguous part of an array or string:

  • "Find the maximum sum of any 3 consecutive elements."

  • "Find the longest substring without repeating characters."

  • "Find the smallest subarray whose sum is at least 7."

A brute-force solution checks every subarray, which is often O(n²) or worse. A sliding window solves these in O(n).


What is a Sliding Window?

A sliding window is a range of consecutive elements, marked by a left and a right index, that moves across the array. Instead of recalculating everything for each new range, we update the result using only the element that enters and the element that leaves.

A window is just a subarray from index left to index right:

Index:   0   1   2   3   4   5
Array: [ 2,  1,  5,  1,  3,  2 ]
             └───────┘
             left=1   right=3
             window = [1, 5, 1]

The window size is right - left + 1.

In the previous chapter you learned the Two Pointers technique. A sliding window is a special case of same-direction two pointers, where left and right mark the two ends of a window.

There are two kinds of sliding windows:

Type

Window size

Example question

Fixed-size window

Always exactly k

Maximum sum of any k consecutive elements

Variable-size window

Grows and shrinks

Longest or shortest subarray that satisfies a condition


Fixed-Size Sliding Window

The Problem

Problem: Given an array and a number k, find the maximum sum of any k consecutive elements.

arr = [2, 1, 5, 1, 3, 2],  k = 3

All windows of size 3 are:

[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9   ← maximum
[1, 3, 2] → 6

The Brute-Force Approach

For every starting index, add up the next k elements. There are about n windows, and each takes k additions, so the time complexity is O(n × k). When k is close to n / 2, this becomes O(n²).

The Key Observation

Look at two neighbouring windows:

Window 1: [2, 1, 5]        sum = 8
Window 2:    [1, 5, 1]     sum = ?

The elements 1 and 5 are in both windows. Why add them again?

When the window slides one step to the right:

  • One element leaves from the left (2).

  • One element enters from the right (1).

So:

new sum = old sum + entering element - leaving element
        = 8 + 1 - 2
        = 7

Each slide costs just O(1) work.

Step by Step

Build first window: 2 + 1 + 5 = 8            best = 8

Slide: add arr[3]=1, remove arr[0]=2 → 7     best = 8
Slide: add arr[4]=3, remove arr[1]=1 → 9     best = 9
Slide: add arr[5]=2, remove arr[2]=5 → 6     best = 9

Fixed Window in Java

class Main {

    static int maxSumBrute(int[] arr, int k) {

        int best = Integer.MIN_VALUE;

        for (int start = 0; start <= arr.length - k; start++) {

            int sum = 0;

            for (int i = start; i < start + k; i++) {
                sum += arr[i];
            }

            best = Math.max(best, sum);
        }

        return best;
    }

    static int maxSumWindow(int[] arr, int k) {

        int windowSum = 0;

        // Build the first window
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int best = windowSum;

        // Slide the window
        for (int right = k; right < arr.length; right++) {

            windowSum += arr[right];      // add the new element
            windowSum -= arr[right - k];  // remove the old element

            best = Math.max(best, windowSum);
        }

        return best;
    }

    public static void main(String[] args) {

        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;

        System.out.println("Brute force: " + maxSumBrute(arr, k));
        System.out.println("Sliding window: " + maxSumWindow(arr, k));
    }
}

Output:

Brute force: 9
Sliding window: 9

The sliding window version runs in O(n) time and O(1) space, no matter how big k is.

Notice the index of the element leaving the window: when right enters, the element at right - k leaves. Getting this index wrong by one is the most common bug in fixed windows.

Example: Find All Anagrams in a String

The "window" does not have to hold a sum. It can hold anything we can update in O(1) when an element enters or leaves, such as character counts.

Problem: Given strings s and p (lowercase letters only), return all starting indexes in s where an anagram of p begins.

An anagram of p has the same length as p and the same count of each letter. So we slide a window of size p.length() over s and keep a count array of size 26 for the window.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Main {

    static List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<>();

        int k = p.length();

        if (k > s.length()) {
            return result;
        }

        int[] need = new int[26];
        int[] window = new int[26];

        for (int i = 0; i < k; i++) {
            need[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(need, window)) {
            result.add(0);
        }

        for (int right = k; right < s.length(); right++) {

            window[s.charAt(right) - 'a']++;       // add new char
            window[s.charAt(right - k) - 'a']--;   // remove old char

            if (Arrays.equals(need, window)) {
                result.add(right - k + 1);         // window start
            }
        }

        return result;
    }

    public static void main(String[] args) {

        System.out.println(findAnagrams("cbaebabacd", "abc"));
        System.out.println(findAnagrams("abab", "ab"));
    }
}

Output:

[0, 6]
[0, 1, 2]

For "cbaebabacd", the windows starting at index 0 ("cba") and index 6 ("bac") are anagrams of "abc".

Comparing two arrays of size 26 is a constant amount of work, so the whole algorithm is O(26 × n), which is O(n).


Variable-Size Sliding Window

In many problems we do not know the window size in advance. Instead, we want the longest or shortest window that satisfies some condition.

The general idea:

  1. Expand: move right forward and add the new element to the window.

  2. Shrink: while the window breaks the rule (or while it is still valid, for "shortest" problems), remove arr[left] and move left forward.

  3. Record: update the answer at the right moment.

Here is the general template:

int left = 0;

for (int right = 0; right < n; right++) {

    // 1. Add arr[right] to the window

    while (/* window needs shrinking */) {
        // 2. Remove arr[left] from the window
        left++;
    }

    // 3. Update the answer using right - left + 1
}

Example: Smallest Subarray with Sum at Least Target

Problem: Given an array of positive integers and a target, find the length of the smallest contiguous subarray whose sum is greater than or equal to target. Return 0 if there is none.

nums = [2, 3, 1, 2, 4, 3],  target = 7

We keep expanding until the sum reaches the target. Then, while the window is still valid, we record its length and shrink from the left to see if a smaller window also works.

right=0: window [2]             sum=2
right=1: window [2,3]           sum=5
right=2: window [2,3,1]         sum=6
right=3: window [2,3,1,2]       sum=8 ≥ 7 → length 4, remove 2 → sum=6
right=4: window [3,1,2,4]       sum=10 ≥ 7 → length 4, remove 3 → sum=7
         window [1,2,4]         sum=7 ≥ 7 → length 3, remove 1 → sum=6
right=5: window [2,4,3]         sum=9 ≥ 7 → length 3, remove 2 → sum=7
         window [4,3]           sum=7 ≥ 7 → length 2, remove 4 → sum=3

Smallest length = 2   ([4, 3])
class Main {

    static int minSubarrayLen(int target, int[] nums) {

        int left = 0;
        int sum = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {

            sum += nums[right];                 // expand

            while (sum >= target) {             // window is valid
                best = Math.min(best, right - left + 1);
                sum -= nums[left];              // shrink
                left++;
            }
        }

        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {

        int[] nums = {2, 3, 1, 2, 4, 3};

        System.out.println(minSubarrayLen(7, nums));
        System.out.println(minSubarrayLen(100, nums));
    }
}

Output:

2
0

Why Is This O(n) When There Is a Loop Inside a Loop?

This confuses many students. The inner while loop does not restart from the beginning each time. The left pointer only ever moves forward, and it can move at most n times in total across the whole program.

right moves n times
left  moves at most n times
Total work = O(n + n) = O(n)

Every element is added to the window once and removed at most once.

Example: Longest Substring Without Repeating Characters

This is one of the most asked interview questions.

Problem: Given a string s, find the length of the longest substring that has no repeating characters.

"abcabcbb" → "abc"  → 3
"bbbbb"    → "b"    → 1
"pwwkew"   → "wke"  → 3

We keep a count of each character inside the window. When the new character makes a count greater than 1, the window has a repeat, so we shrink from the left until that character appears only once again.

We assume the string contains ASCII characters, so an int[128] array works as a counter. (For other character sets, a HashMap is used instead, which you will learn later.)

class Main {

    static int longestUniqueSubstring(String s) {

        int[] count = new int[128];   // one counter for each ASCII character

        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {

            char c = s.charAt(right);
            count[c]++;

            // Shrink until c appears only once in the window
            while (count[c] > 1) {
                count[s.charAt(left)]--;
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }

    public static void main(String[] args) {

        System.out.println(longestUniqueSubstring("abcabcbb"));
        System.out.println(longestUniqueSubstring("bbbbb"));
        System.out.println(longestUniqueSubstring("pwwkew"));
        System.out.println(longestUniqueSubstring(""));
    }
}

Output:

3
1
3
0

Let's trace "pwwkew":

right=0 'p': window "p"     best=1
right=1 'w': window "pw"    best=2
right=2 'w': 'w' repeats → remove 'p', remove 'w' → window "w"   best=2
right=3 'k': window "wk"    best=2
right=4 'e': window "wke"   best=3
right=5 'w': 'w' repeats → remove 'w' → window "kew"             best=3

Note that the answer must be a substring (contiguous). "pwke" is a subsequence, not a substring, so it does not count.

Example: Max Consecutive Ones with K Flips

Problem: Given a binary array nums and an integer k, return the maximum number of consecutive 1s if you can flip at most k zeros.

Rephrase it: find the longest window that contains at most k zeros. That is a classic variable window.

class Main {

    static int longestOnes(int[] nums, int k) {

        int left = 0;
        int zeros = 0;
        int best = 0;

        for (int right = 0; right < nums.length; right++) {

            if (nums[right] == 0) {
                zeros++;
            }

            while (zeros > k) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};

        System.out.println(longestOnes(nums, 2));
    }
}

Output:

6

With k = 2, one best window is from index 4 to index 9: [0, 0, 1, 1, 1, 1]. It contains exactly two zeros. Flip them and you get six consecutive 1s.


Longest vs Shortest Window

The template changes slightly depending on what we want:

Longest window

Shortest window

Shrink while...

the window is invalid

the window is valid

Update answer...

after shrinking (window is valid again)

inside the shrink loop (before removing)

Examples

Longest substring without repeats, max ones with k flips

Smallest subarray with sum ≥ target, minimum window substring


When Does Sliding Window NOT Work?

A variable window works only when the condition behaves "nicely":

  • Adding an element moves the window towards breaking the rule (or satisfying it).

  • Removing an element moves it back.

For "smallest subarray with sum ≥ target", this is true only if all numbers are positive. With negative numbers, adding an element can decrease the sum, and shrinking can increase it, so the window logic breaks.

For example, take nums = [5, -10, 6] and target = 6. The window [5, -10] has sum -5, which is below the target, so the template keeps expanding. After adding 6, the sum is only 1, the window never becomes valid, and the code returns 0. But the subarray [6] alone has sum 6, so the correct answer is 1. The negative number made the window sum go down when we expanded, which breaks the logic of the template. Problems such as "count subarrays with sum equal to k" when negative numbers are allowed are solved with Prefix Sums instead.

You will learn the Prefix Sum technique in the next chapter.

Also remember that sliding window is for contiguous subarrays and substrings. If the problem talks about subsequences or subsets (where elements can be skipped), a sliding window usually does not apply.


Time and Space Complexity

Problem

Brute Force

Sliding Window

Space

Max sum of size-k window

O(n × k)

O(n)

O(1)

Find all anagrams

O(n × m)

O(n)

O(1) (26 counters)

Smallest subarray with sum ≥ target

O(n²)

O(n)

O(1)

Longest substring without repeats

O(n²) or worse

O(n)

O(1) (128 counters)

Max consecutive ones with k flips

O(n²)

O(n)

O(1)


How to Recognise a Sliding Window Problem

Look for these clues in the problem statement:

  • The words subarray, substring, consecutive or contiguous.

  • "Of size k" (fixed window).

  • "Longest", "shortest", "maximum length", "minimum length" with a condition (variable window).

  • "At most k distinct", "at most k zeros", "without repeating" (variable window).

  • All numbers are positive (a strong hint that a sum-based window will work).


Common Mistakes

1. Off-by-One in the Leaving Index

In a fixed window of size k, when arr[right] enters, arr[right - k] leaves. Not right - k + 1, not right - k - 1.

2. Wrong Window Length

The length of the window from left to right (inclusive) is right - left + 1. Forgetting the + 1 is very common.

3. Using if Instead of while to Shrink

Sometimes the window must shrink by several positions at once (as in the "pwwkew" trace). An if only removes one element and leaves the window invalid.

4. Applying It with Negative Numbers

Sum-based variable windows assume non-negative numbers. Check the constraints before choosing this technique.

5. Forgetting the "No Answer" Case

In "smallest subarray" problems, the answer might not exist. Start with Integer.MAX_VALUE and return 0 (or whatever the problem asks) if it never changed.


Practice Problems

  1. Maximum Average Subarray I

  2. Maximum Sum of Distinct Subarrays With Length K

  3. Find All Anagrams in a String

  4. Permutation in String

  5. Minimum Size Subarray Sum

  6. Longest Substring Without Repeating Characters

  7. Max Consecutive Ones III

  8. Longest Repeating Character Replacement

  9. Fruit Into Baskets

  10. Minimum Window Substring (hard)


The Main Idea

A sliding window keeps track of a range of consecutive elements and updates the answer using only the element that enters and the element that leaves.

Fixed window:
    add arr[right], remove arr[right - k]

Variable window:
    expand right → shrink left while needed → record answer

Because each element enters the window once and leaves it at most once, sliding window solutions run in:

O(n) time

Whenever a problem asks about the best contiguous subarray or substring, think sliding window first: expand with the right pointer, shrink with the left pointer, and never recalculate what you already know.