Why should you care?
Many programming problems involve finding something inside a contiguous portion of an array or string.
For example:
- Find the maximum sum of
kconsecutive elements. - Find the longest substring without repeating characters.
- Find the smallest subarray whose sum reaches a target.
- Find the number of subarrays satisfying a condition.
- Find the longest sequence containing at most
kdistinct values.
A naive solution often checks every possible subarray.
For an array of size n, there can be:
n(n + 1) / 2
different subarrays.
That's:
O(n²)
The Sliding Window Technique can often reduce these problems to:
O(n)
The core idea is:
Instead of repeatedly calculating overlapping ranges from scratch, maintain a window and slide it across the data.
The Problem
Suppose we have:
[2, 1, 5, 1, 3, 2]
and we want:
Find the maximum sum of
3consecutive elements.
A brute-force solution examines:
[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9
[1, 3, 2] → 6
Answer:
9
But notice what happens between consecutive windows:
[2, 1, 5]
↓
[1, 5, 1]
We don't need to calculate the second sum from scratch.
The old window was:
2 + 1 + 5 = 8
Remove:
2
Add:
1
Therefore:
8 - 2 + 1 = 7
This is the fundamental idea behind the Sliding Window Technique.
The Concept
A sliding window represents a range of elements currently being considered.
For example:
Array:
[2, 1, 5, 1, 3, 2]
↑ ↑
left right
The elements between left and right form the current window.
Instead of repeatedly creating new subarrays, we move the boundaries:
Window 1:
[2, 1, 5] 1 3 2
↑ ↑
L R
Window 2:
2 [1, 5, 1] 3 2
↑ ↑
L R
Window 3:
2 1 [5, 1, 3] 2
↑ ↑
L R
The window slides from left to right.
Simple Explanation
Imagine looking through a window on a moving train.
You can only see a few objects at a time.
As the train moves:
Old view:
[A B C]
Move:
[B C D]
Move:
[C D E]
You don't completely forget everything you saw.
You:
Remove A
Add D
The Sliding Window Technique works the same way.
Remove something from the left
+
Add something on the right
=
Move the window efficiently
Real-world Analogy
Imagine monitoring website traffic every 5 minutes.
Suppose the data is:
10 20 15 30 25 40
You want the total traffic for every 3-minute window.
First:
10 + 20 + 15 = 45
Move one position:
20 + 15 + 30
Instead of recalculating:
45 - 10 + 30 = 65
Move again:
65 - 20 + 25 = 70
The window continuously moves while maintaining the necessary information.
That's why the technique is so efficient.
Code Example
Let's solve the fixed-size maximum-sum problem.
Given:
[2, 1, 5, 1, 3, 2]
Find the maximum sum of k = 3 consecutive elements.
Brute Force
A straightforward solution is:
public static int maxSumBruteForce(int[] nums, int k) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i <= nums.length - k; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) {
sum += nums[j];
}
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
Complexity:
Time: O(n × k)
If k is large, this becomes expensive.
Sliding Window Solution
public static int maxSum(int[] nums, int k) {
int windowSum = 0;
// Build the first window
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
// Slide the window
for (int right = k; right < nums.length; right++) {
windowSum += nums[right];
windowSum -= nums[right - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
For:
[2, 1, 5, 1, 3, 2]
the windows are:
[2, 1, 5] → 8
[1, 5, 1] → 7
[5, 1, 3] → 9
[1, 3, 2] → 6
Result:
9
Complexity
Time: O(n)
Space: O(1)
We process each element only a constant number of times.
Common Mistakes
Mistake 1: Recalculating the entire window
This defeats the purpose of the technique.
Bad:
Window 1 → calculate everything
Window 2 → calculate everything again
Window 3 → calculate everything again
Instead:
New Window = Old Window - Removed Element + Added Element
Reuse what you've already calculated.
Mistake 2: Confusing subarray with subsequence
Sliding Window generally works with contiguous ranges.
For:
[1, 2, 3, 4]
These are subarrays:
[1, 2]
[2, 3]
[3, 4]
[1, 2, 3]
But:
[1, 3]
is not a contiguous subarray.
It is a subsequence.
This distinction matters.
Mistake 3: Moving both pointers incorrectly
In variable-size windows, we often use:
left
right
The right pointer expands the window:
right++
The left pointer shrinks it:
left++
A common pattern is:
while (conditionIsInvalid()) {
// remove nums[left]
left++;
}
Incorrect pointer movement can cause:
- Missing valid windows
- Infinite loops
- Incorrect answers
Advanced Notes
1. Fixed-Size Sliding Window
The easiest version has a window of exactly k elements.
Example:
Find maximum sum of k consecutive elements.
The window always has:
size = k
Pattern:
for (int right = k; right < n; right++) {
window += nums[right];
window -= nums[right - k];
}
The general idea:
Add right
Remove left
2. Variable-Size Sliding Window
Sometimes the window size is not fixed.
Instead, we expand and shrink based on a condition.
For example:
Find the smallest subarray whose sum is at least
7.
Input:
[2, 3, 1, 2, 4, 3]
We can use:
left = 0
right = 0
Expand:
[2] sum = 2
[2,3] sum = 5
[2,3,1] sum = 6
[2,3,1,2] sum = 8
Now the condition is satisfied.
Shrink from the left:
[3,1,2] sum = 6
Too small.
So expand again.
Eventually:
[4,3]
has sum:
7
Length:
2
So the answer is 2.
3. Variable Window Code
public static int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(
minLength,
right - left + 1
);
sum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE
? 0
: minLength;
}
For:
target = 7
nums = [2,3,1,2,4,3]
Result:
2
because:
[4,3]
is the smallest valid window.
4. Two Pointer Relationship
Sliding Window is closely related to the Two Pointer Technique.
Typical structure:
left → beginning of window
right → end of window
Both move toward the right:
left →→→
right →→→
This often gives linear complexity.
You can think of Sliding Window as a specialized form of two pointers where the pointers define a contiguous range.
5. Longest Substring Without Repeating Characters
Sliding Window becomes particularly powerful with strings.
Consider:
"abcabcbb"
We want the longest substring without repeating characters.
The answer is:
"abc"
Length:
3
We can maintain a window:
[a b c]
When another a appears:
[a b c a]
the window becomes invalid.
So we move left forward until the duplicate is removed.
Using a HashSet:
import java.util.*;
public class Main {
static int longestUniqueSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLength = Math.max(
maxLength,
right - left + 1
);
}
return maxLength;
}
public static void main(String[] args) {
System.out.println(
longestUniqueSubstring("abcabcbb")
);
}
}
Output:
3
Complexity:
Time: O(n)
Space: O(min(n, character-set-size))
The important pattern is:
Expand
↓
Constraint violated?
↓
Shrink
↓
Constraint satisfied
↓
Continue
6. Frequency Maps
Many string problems require knowing how frequently characters occur.
For example:
Find the smallest substring containing all characters of a target string.
A frequency map can maintain the window state:
Map<Character, Integer>
As the window expands:
Add character
As it shrinks:
Remove character
This combination is extremely common:
Sliding Window
+
HashMap
7. At Most K Distinct Characters
Consider:
"eceba"
Suppose:
k = 2
Find the longest substring containing at most two distinct characters.
We maintain:
left
right
frequency map
When the number of distinct characters becomes greater than k:
while (distinct > k) {
remove s[left]
left++
}
This pattern appears in many interview problems.
8. Maximum/Minimum in a Sliding Window
Some problems ask:
Find the maximum value in every window of size
k.
For:
[1, 3, -1, -3, 5, 3, 6, 7]
with:
k = 3
the result is:
[3, 3, 5, 5, 6, 7]
A simple sliding window would repeatedly scan the window, giving:
O(nk)
But we can use a Deque to maintain candidates for the maximum.
Then the solution becomes:
O(n)
This connects the Sliding Window Technique with another data structure you have already learned: the Deque.
9. When Sliding Window Works
Sliding Window is especially useful when:
The problem involves:
↓
Contiguous subarray
OR
Contiguous substring
and we can efficiently maintain the information needed for the current window.
Typical clues include:
"subarray"
"substring"
"consecutive"
"contiguous"
"longest"
"shortest"
"maximum"
"minimum"
"at most K"
"exactly K"
These should immediately make you consider Sliding Window.
10. When Sliding Window Doesn't Work
Sliding Window is not a universal technique.
For example, arbitrary subsequences don't naturally form a single contiguous window.
Also, some conditions cannot be maintained efficiently when moving the window.
Always ask:
Can I update the answer when one element enters and another leaves?
If yes, Sliding Window may work.
11. Time Complexity
The most important property of variable-size Sliding Window is that the pointers generally move only forward.
For example:
right → n movements
left → n movements
Therefore:
Total movements ≤ 2n
So:
Time = O(n)
Even though there is a nested while loop:
for (...) {
while (...) {
left++;
}
}
the complexity is usually still O(n).
Why?
Because left doesn't reset.
It moves forward at most n times.
This is an important example of amortized analysis.
12. A General Sliding Window Template
For variable-size problems, remember this structure:
int left = 0;
for (int right = 0; right < n; right++) {
// Add nums[right]
addToWindow(nums[right]);
while (windowIsInvalid()) {
// Remove nums[left]
removeFromWindow(nums[left]);
left++;
}
// Window is valid here
updateAnswer();
}
Think of it as:
EXPAND
↓
CHECK
↓
SHRINK if necessary
↓
RECORD ANSWER
This template solves a surprisingly large number of problems.
The Bigger Picture
Your algorithmic progression is now moving from individual algorithms toward problem-solving patterns:
Arrays
↓
Linked Lists
↓
Stacks / Queues
↓
Trees / Graphs
↓
Searching
↓
Sorting
↓
DFS / BFS
↓
Greedy
↓
Dynamic Programming
↓
Backtracking
↓
Sliding Window
Sliding Window is different from algorithms such as Merge Sort or BFS.
It is better understood as a problem-solving technique.
You recognize a particular structure in a problem:
Contiguous range
+
Information about the range
+
Efficient update when range moves
↓
Sliding Window
It also connects multiple concepts you've already learned:
Sliding Window
+
Two Pointers
+
Hash Tables
+
Queues / Deques
↓
Efficient Range Processing
This is an important transition toward learning common coding interview patterns.
The Most Important Mental Model
Remember:
RIGHT
↓
[A B C D E F G H]
↑ ↑
LEFT WINDOW
Expand →
When the window becomes invalid:
RIGHT
↓
[A B C D E F G H]
↑ ↑
LEFT WINDOW
Shrink ←
The complete mental model is:
Expand the window to explore more elements. When the window violates the condition, shrink it from the left until it becomes valid again.
For fixed-size windows:
ADD RIGHT
REMOVE LEFT
For variable-size windows:
EXPAND RIGHT
SHRINK LEFT WHEN NEEDED
That distinction is enough to recognize many Sliding Window problems.
Summary
The Sliding Window Technique efficiently processes contiguous portions of arrays and strings.
Key ideas:
- A window represents a contiguous range.
- Instead of recalculating each range, maintain the current window's state.
- Fixed-size windows always contain
kelements. - Variable-size windows expand and shrink according to a condition.
- Two pointers usually represent the left and right boundaries.
- HashMaps and HashSets are frequently used with Sliding Window.
- Deques can efficiently solve advanced window maximum/minimum problems.
- Many variable-size solutions run in
O(n)because each pointer moves forward at mostntimes. - Common applications include maximum sums, minimum subarrays, longest substrings, frequency problems, and constraint-based ranges.
- Sliding Window is particularly useful when the problem involves contiguous or consecutive elements.
Top comments (0)