DSA Patterns Made Simple · Arrays and Strings: The Six Core Patterns
Sliding Window
For 'longest', 'shortest' or 'best' contiguous stretch problems, slide a window over the array, growing on the right and shrinking on the left, instead of checking every subarray.
The problem
Longest Substring Without Repeating Characters: in "abcabcbb", the longest stretch with no repeated letter is "abc", length 3.
Checking every substring is O(n²) substrings, each checked for repeats. But notice: when a stretch hits a repeated letter, you don't need to start over. You just drop letters from the left until the repeat is gone and keep going.
How to spot it
- Contiguous subarray or substring (the words "substring", "subarray", "consecutive", "window")
- "Longest / shortest / maximum sum of a stretch that satisfies a rule"
- A rule that stays true or false as the stretch grows or shrinks (no repeats, sum ≤ k, at most k distinct)
- Fixed size: "every window of size k"
The idea
Keep a window [left, right]. Move right forward one step at a time to grow the window. Whenever the window breaks the rule, move left forward to shrink it until the rule holds again. After each step, record the best window seen.
Both pointers only move forward, so each element enters and leaves the window at most once: O(n).
For a fixed-size window, add the new element on the right and remove the one falling off on the left, keeping a running total.
The template
left = 0
best = 0
for right in range(len(arr)):
add(arr[right]) # grow
while window_is_invalid():
remove(arr[left]) # shrink
left += 1
best = max(best, right - left + 1)
let left = 0, best = 0;
for (let right = 0; right < arr.length; right++) {
add(arr[right]); // grow
while (windowIsInvalid()) {
remove(arr[left]); // shrink
left++;
}
best = Math.max(best, right - left + 1);
}
Worked example
A variable window (longest substring without repeats), a fixed window (best average of k days) and the buy-low-sell-high stock problem, which is a window whose left edge is the cheapest day so far.
def longest_unique_substring(s):
in_window = set()
left = best = 0
for right, ch in enumerate(s):
while ch in in_window: # the rule broke: shrink from the left
in_window.remove(s[left])
left += 1
in_window.add(ch)
best = max(best, right - left + 1)
return best
def max_sum_of_k(nums, k):
window = sum(nums[:k])
best = window
for right in range(k, len(nums)):
window += nums[right] - nums[right - k] # add new, drop the oldest
best = max(best, window)
return best
def max_profit(prices):
cheapest = prices[0]
best = 0
for p in prices[1:]:
best = max(best, p - cheapest) # sell today
cheapest = min(cheapest, p) # or remember a cheaper buy day
return best
print("longest without repeats in abcabcbb:", longest_unique_substring("abcabcbb"))
print("longest without repeats in pwwkew:", longest_unique_substring("pwwkew"))
print("best 3-day total:", max_sum_of_k([2, 1, 5, 1, 3, 2], 3))
print("best stock profit:", max_profit([7, 1, 5, 3, 6, 4]))
Output
longest without repeats in abcabcbb: 3 longest without repeats in pwwkew: 3 best 3-day total: 9 best stock profit: 5
function longestUniqueSubstring(s) {
const inWindow = new Set();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
while (inWindow.has(s[right])) { // the rule broke: shrink from the left
inWindow.delete(s[left]);
left++;
}
inWindow.add(s[right]);
best = Math.max(best, right - left + 1);
}
return best;
}
function maxSumOfK(nums, k) {
let window = nums.slice(0, k).reduce((a, b) => a + b, 0);
let best = window;
for (let right = k; right < nums.length; right++) {
window += nums[right] - nums[right - k]; // add new, drop the oldest
best = Math.max(best, window);
}
return best;
}
function maxProfit(prices) {
let cheapest = prices[0], best = 0;
for (const p of prices.slice(1)) {
best = Math.max(best, p - cheapest); // sell today
cheapest = Math.min(cheapest, p); // or remember a cheaper buy day
}
return best;
}
console.log("longest without repeats in abcabcbb:", longestUniqueSubstring("abcabcbb"));
console.log("longest without repeats in pwwkew:", longestUniqueSubstring("pwwkew"));
console.log("best 3-day total:", maxSumOfK([2, 1, 5, 1, 3, 2], 3));
console.log("best stock profit:", maxProfit([7, 1, 5, 3, 6, 4]));
Output
longest without repeats in abcabcbb: 3 longest without repeats in pwwkew: 3 best 3-day total: 9 best stock profit: 5
Common mistakes
- Using a window on non-contiguous problems. "Subsequence" (items can be skipped) is not a window problem; it's often dynamic programming.
ifinstead ofwhilewhen shrinking. One step left may not fix the window; keep shrinking until it's valid.- Recording the answer at the wrong time. For "longest", record after the window is valid again; for "shortest", record while it's still valid, just before shrinking.
- Windows with negative numbers. "Sum ≤ k" windows assume adding items only increases the sum; with negatives, use prefix sums instead.
Practice
- Best Time to Buy and Sell Stock (easy)
- Longest Substring Without Repeating Characters (medium)
- Minimum Window Substring (hard): grow until every needed letter is covered, then shrink while it still is.
Key points
- Contiguous + longest/shortest/best → sliding window.
- Grow with
right, shrink withleftwhile invalid, record the best. - Fixed size: add the new item, subtract the one that falls off.
- O(n) time, because each item enters and leaves the window once.
Practice questions
Why is the sliding window O(n) even though it has a while loop inside a for loop?
Answer
The left pointer only moves forward and never past the right one, so across the whole run it moves at most n times. Together the two pointers make at most 2n moves.
When does a 'sum at most k' sliding window stop working?
Answer
When the array has negative numbers: adding an element may reduce the sum, so shrinking the window no longer reliably fixes it. Use prefix sums with a hash map instead.
Open in the app to mark lessons complete, take notes and track your progress.