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 | Maximum sum of any |
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 = 3All windows of size 3 are:
[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9 ← maximum
[1, 3, 2] → 6The 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
= 7Each 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 = 9Fixed 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: 9The 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:
Expand: move
rightforward and add the new element to the window.Shrink: while the window breaks the rule (or while it is still valid, for "shortest" problems), remove
arr[left]and moveleftforward.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 = 7We 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
0Why 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" → 3We 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
0Let'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=3Note 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:
6With 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 |
|
|
|
Find all anagrams |
|
|
|
Smallest subarray with sum ≥ target |
|
|
|
Longest substring without repeats |
|
|
|
Max consecutive ones with k flips |
|
|
|
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
kdistinct", "at mostkzeros", "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
Maximum Average Subarray I
Maximum Sum of Distinct Subarrays With Length K
Find All Anagrams in a String
Permutation in String
Minimum Size Subarray Sum
Longest Substring Without Repeating Characters
Max Consecutive Ones III
Longest Repeating Character Replacement
Fruit Into Baskets
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 answerBecause each element enters the window once and leaves it at most once, sliding window solutions run in:
O(n) timeWhenever 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.