Sliding Window Technique: DSA Mental Frameworks Series
Understanding frameworks for solving DSA problems! A one-stop guide to get started on Sliding Windows
Mastering Sliding Window Algorithms: A Structured Guide to Fixed & Dynamic Windows
Sliding window techniques are essential for efficiently solving array and string problems where you need to analyse contiguous subarrays or substrings. These problems often appear in coding interviews and competitive programming, requiring optimal solutions with O(n) time complexity.
In this guide, we’ll break down sliding window patterns into two core types:
Fixed-Size Windows: For problems where the window length is predetermined (e.g., finding maximum subarray sums of size
k).Dynamic-Size Windows: For problems where the window expands/shrinks based on conditions (e.g., finding the smallest subarray with a sum ≥
target).
We’ll explore:
Key insights to identify sliding window problems.
Step-by-step templates for both fixed and dynamic windows.
Real-world examples from Leetcode (with Java/Python code).
Common pitfalls and optimization tricks.
Whether you’re tackling "Fruit Into Baskets" (Leetcode 904) or "Longest Substring Without Repeats" (Leetcode 3), this guide will equip you with a systematic approach to sliding windows.
🔥 To save your time in searching from CHATGPT and DEEPSEEK for the same, I have attached the notes here so you don’t have to leave 🙂
Basics and Types
Two types of Sliding window problems:
Fixed length
Dynamic length
Usually the pattern of sliding window is a dead give away from the problem definition.
More on #2 Dynamic Length Sliding Window approach
Keeps growing the window from the right end based on some condition
Ask few questions and store results for the current window
Shrink the window from left based on some other conditions
Advantage and Alternative?
Alternative naive approach is brute force to identify all possible intervals (for every start, find an end such that end > start) and then finding if solution works.
This is another way of saying for each length identify all start points and analyse to find a solution.
Issue → Duplicating effort → We see and calculate results for the part of the array multiple times.
Simplest Fixed Window problem
Maximum sum contiguous sub-arrary of size k
Two types of Dynamic Window problem:
Simple:
Find a window such that Smallest sum ≥ some given sum value = S
With Auxiliary Data structure:
Eg.1. Longest substring with no more than k distinct characters — here we need to maintain hash-set/hash-map to remember (and un-remember) the distinct characters seen till now.
Eg.2. String permutations - Does a string occur as a permutation in a given other string.
Important Example for Dynamic Window Problem with Auxiliary Data Structures:
https://leetcode.com/problems/fruit-into-baskets/description/
Maximum number of fruits (longest window) such that number of fruit types in the window is not greater than 2
Max tracker will be based on length of window
Invariant - given window will only have less than or equal to 2 types of fruits. Update done when this invariant is maintained.
Expand from right when invariant is maintained.
Shrinking will remove fruits from basket but will not reset available basket until all fruits of the type removed - window needs to update until this happens to maintain invariance
class Solution {
public int totalFruit(int[] fruits) {
HashMap<Integer, Integer> count = new HashMap<>();
int i = 0; int j = 0;
int max_cnt = 0;
while (j < fruits.length) {
// Add the current fruit, this might break the invariant
int fruit = fruits[j];
count.put(fruit, count.getOrDefault(fruit, 0) + 1);
if (count.size() <= 2) {
// try go update when invariant is holding
max_cnt = Math.max(max_cnt, j - i + 1);
}
// If invariant not maintained
// Shrink when total number of fruit types possible is greater than allowed (trying to maintain the invariant)
// Since find max problem no need to update max tracker while shrinking
while (count.size() > 2) {
int leftFruit = fruits[i];
count.put(leftFruit, count.get(leftFruit) - 1);
if (count.get(leftFruit) == 0) {
count.remove(leftFruit);
}
i++;
}
j++;
}
return max_cnt;
}
}
Commonalities
Giveaways:
Sequential data inferences - grouped sequential data.
Subarray, contiguos subarrays
Longest / Smallest / Min / Max / Contains
Solving - Building around the window (focus on the window):
Fix one or two criteria the window building needs to adhere to and fix the data points / inferences to make on each window.
Eg. Maximum Sum with Size k; Longest substring with ≤ k distinct characters;
Things to keep in mind for implementation:
Start by thinking about the constraints on which window can be built and moved
Finding the Invariant for the Window - Think roughly on the data points that can be collected on each window
For dynamic length window problems:
Start implementation by expanding from right until we get to the end OR the condition on which we need to stop growing as our invariant is changing now.
For above step firstly ASK the questions that needs to be asked - calculate the result for this window at the start of the loop. Update the inferences (example max/min/longest/shortest/number of distinct/hash-sets update etc)
Secondly, do the check mentioned in (a) whether or not the window can be increased in length
If not, we have the case where we need to shrink until we get to the end pointer OR the condition on which we need to stop shrinking as we found the next viable window
🔥 General Sliding Window problems:
Fixed Window: Slide the window of size
kacross the input, updating metrics incrementally.Variable Window:
Minimum: Expand until the condition is met, then contract to find the smallest valid window.
Maximum: Expand until the condition is violated, then adjust to maintain validity and track the largest window.
🔥 Two things to keep an eye out for:
When invariant is maintained try do the update to the min/max tracker
There can be a missed update AFTER the last iteration, so in case it is required, add the loop max/min update step once more AFTER the loop.
CHATGPT NOTES
General Template for Sliding Window Problems
Initialize Variables:
Initialize two pointers (usually
startandend) to define the current window.Other variables to hold results, such as
min_length,max_length, or the desired sums/counts.
Expand the Window:
Use the
endpointer to expand the window by iterating through the array/string. This typically means moving theendpointer from the start to the end of the collection.Update relevant data structures (like a frequency count or sum) based on the current element.
This is generally applicable for find MAX length questions.
Check Conditions:
After expanding the window, check if the current window meets the required condition (e.g., if the sum exceeds a target, or if a particular count is achieved).
Contract the Window:
If the condition is satisfied, attempt to shrink the window by moving the
startpointer to the right.Update the relevant data structures as you contract the window.
This is generally applicable for find MIN length questions.
During contraction, check if the new window still meets the condition.
Update Result:
If you find a valid window that meets the criteria (e.g., minimum length, maximum length), update your result accordingly.
Repeat:
Continue the above steps until the
endpointer has traversed the entire array/string.
Return the Result:
After the loop ends, return the result, which may be the length of the smallest window, the starting and ending indices, or the window itself, depending on the problem requirements.
Example Problems
Minimum Size Subarray Sum:
Use the template to keep track of the sum of elements in the current window and shrink it when the sum meets or exceeds the target.
Finding Permutation of One String in Another String:
Keep track of character counts using a frequency map (can be an array for fixed character sets) and adjust counts as you slide the window across the string.
Code Example
Here's a simple Python code snippet to illustrate the sliding window template:
def min_subarray_len(target, nums):
start = 0
current_sum = 0
min_length = float('inf')
for end in range(len(nums)):
current_sum += nums[end]# Expand the window
while current_sum >= target:# Condition check
min_length = min(min_length, end - start + 1)# Update result
current_sum -= nums[start]# Contract the window
start += 1# Move start pointer to the right
return min_length if min_length != float('inf') else 0
This structured approach will help you tackle a variety of sliding window problems effectively.
DEEPSEEK NOTES
To solve sliding window problems efficiently, follow these structured templates based on whether the window size is fixed or variable. Below are the general templates along with examples to illustrate each case.
1. Fixed Window Size Template
Use this when the problem requires checking all possible windows of a specific size (e.g., finding permutations or anagrams).
Steps:
Precompute Target Metrics: Calculate the target's properties (e.g., frequency map of characters).
Initialise Window: Set up the initial window with the first
kelements and compute its metrics.Check Initial Window: Compare the initial window's metrics with the target.
Slide the Window: Move the window one element at a time, adjusting the metrics and checking if the condition is met.
Example: Check if a permutation of s1 exists in s2
python
from collections import Counter
def check_inclusion(s1, s2):
k = len(s1)
target = Counter(s1)
window = Counter(s2[:k])
if window == target:
return True
for i in range(k, len(s2)):
left_char = s2[i - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
right_char = s2[i]
window[right_char] += 1
if window == target:
return True
return False
2. Variable Window Size Template
Use this when the window size is not fixed, typically for finding the minimum or maximum subarray/substring that meets a condition.
a. Minimum Window (e.g., Minimum Subarray Sum)
Steps:
Initialise Pointers:
left = 0, variables to track current state (e.g., sum).Expand Window: Move
rightto include elements until the condition is met.Contract Window: Once the condition is met, shrink from the left to find the minimum valid window.
Example: Minimum size subarray sum ≥ target
python
def min_subarray_len(target, nums):
left = 0
current_sum = 0
min_length = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return min_length if min_length != float('inf') else 0
b. Maximum Window (e.g., Longest Substring Without Repeating Characters)
Steps:
Initialise Pointers:
left = 0, variables to track current state (e.g., character frequencies).Expand Window: Move
rightuntil the condition is violated.Contract Window: Adjust
leftto restore the condition, then update the maximum length.
Example: Longest substring without repeating characters
python
def length_of_longest_substring(s):
left = 0
max_len = 0
char_index = {}
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1
char_index[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
Key Takeaways:
Fixed Window: Slide the window of size
kacross the input, updating metrics incrementally.Variable Window:
Minimum: Expand until the condition is met, then contract to find the smallest valid window.
Maximum: Expand until the condition is violated, then adjust to maintain validity and track the largest window.
By following these templates, you can systematically approach sliding window problems and adapt them to specific conditions and requirements.
CHATGPT Sample Problems
1. Fixed Size Sliding Window
In this type, the window size is fixed.
Examples:
Problem: Maximum Sum of Subarray of Size K (LeetCode #209)
Problem: Average of Levels in Binary Tree (related to level-wise processing)
Problem: Sliding Window Maximum (LeetCode #239)
Problem: Min Cost Climbing Stairs (Using a fixed-length of steps)
2. Variable Size Sliding Window
Here, the window size can vary and adjusts based on the conditions.
Examples:
Problem: Minimum Size Subarray Sum (LeetCode #209) - DONE
Problem: Longest Substring Without Repeating Characters (LeetCode #3) - DONE
Problem: Longest Substring with At Most K Distinct Characters (LeetCode #340) - PRO ONLY
Problem: Permutations in a String (LeetCode #567)
3. Two Pointers/Sliding Window with Conditions
This involves using a sliding window with two pointers to maintain certain conditions.
Examples:
Problem: Fruit Into Baskets (LeetCode #904)
Problem: Longest Repeating Character Replacement (LeetCode #424)
Problem: Check Inclusions (LeetCode #567)
Problem: Find All Anagrams in a String (LeetCode #438)
4. Contiguous Subarray Problems
These problems often require finding subarrays that meet specific conditions.
Examples:
Problem: Subarray Product Less Than K (LeetCode #713)
Problem: Count of Subarrays with Sum Equal to K (LeetCode #560)
Problem: Winning Coders (related to segments and counting)
Problem: Count Number of Nice Subarrays (LeetCode #1248)
SAMPLE PROBLEMS FROM DEEPSEEK
1. Fixed-Size Sliding Window Examples
(a) Maximum Sum of Subarray of Size K
Problem: Find the maximum sum of any contiguous subarray of size
k4610.Example:
arr = [2, 1, 5, 1, 3, 2], k = 3→ Max sum is9(subarray[5, 1, 3]).Leetcode Equivalent: Maximum Subarray of Size K (GeeksforGeeks).
Key Insight: Slide the window by subtracting the outgoing left element and adding the incoming right element to maintain an
O(n)time complexity 916.
(b) Find All Anagrams in a String
Problem: Given a string
sand a patternp, return all start indices ofp's anagrams ins1314.Example:
s = "cbaebabacd", p = "abc"→ Indices[0, 6].Leetcode Link: 438. Find All Anagrams in a String.
Key Insight: Use a frequency map to track characters in the fixed-size window and compare with the pattern’s map 13.
(c) Permutation in String
Problem: Check if a permutation of
s1exists as a substring ins213.Example:
s1 = "ab", s2 = "eidbaooo"→True("ba" is a permutation).Leetcode Link: 567. Permutation in String.
Key Insight: Use a fixed window of size
len(s1)and compare character counts 1314.
(d) Averages of Subarrays of Size K
Problem: Compute the average of all contiguous subarrays of size
k1016.Example:
arr = [1, 3, 2, 6, -1], k = 3→ Averages[2.0, 3.67, 2.33].Leetcode Equivalent: 643. Maximum Average Subarray I.
Key Insight: Reuse the sum of the previous window to optimize from
O(n*k)toO(n)1016.
2. Variable-Size Sliding Window Examples
(a) Minimum Size Subarray Sum
Problem: Find the smallest contiguous subarray with a sum ≥
target51014.Example:
nums = [2, 3, 1, 2, 4, 3], target = 7→ Minimum length is2([4, 3]).Leetcode Link: 209. Minimum Size Subarray Sum.
Key Insight: Expand the window until the sum meets the target, then shrink from the left to find the minimum 510.
(b) Longest Substring Without Repeating Characters
Problem: Find the length of the longest substring with all unique characters 713.
Example:
s = "abcabcbb"→ Longest substring is"abc"(length3).Leetcode Link: 3. Longest Substring Without Repeating Characters.
Key Insight: Track characters in a hash map and adjust the window when duplicates are found 713.
(c) Longest Substring with At Most K Distinct Characters
Problem: Find the longest substring containing at most
kdistinct characters 1314.Example:
s = "eceba", k = 2→ Longest substring is"ece"(length3).Leetcode Link: 340. Longest Substring with At Most K Distinct Characters.
Key Insight: Use a frequency map to track distinct characters and shrink the window when the count exceeds
k1314.
(d) Maximum Consecutive Ones III
Problem: Find the maximum number of consecutive 1s if you can flip at most
k0s 7.Example:
nums = [1,0,1,1,0], k = 1→ Max length is4(flip the last 0).Leetcode Link: 1004. Max Consecutive Ones III.
Key Insight: Expand until the window has
k+1zeros, then shrink from the left 7.
Additional Practice Problems
Fixed-Size:
239. Sliding Window Maximum (Hard).
567. Permutation in String (Medium).
Variable-Size:
76. Minimum Window Substring (Hard).
These examples cover both pattern recognition and optimization techniques critical for coding interviews.