Efficiently process subarrays or substrings by maintaining a window that expands and contracts.
The sliding window technique maintains a range [left, right] over an array or string. You expand right to include new elements and shrink left to remove invalid ones. This avoids recomputing the window from scratch each time, reducing O(n²) to O(n).
O(n) — each element enters and leaves the window once
O(k) for the window contents
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when every candidate subarray or substring must have exactly size k
Instead of recalculating each window from scratch, add the new right element and remove the old left element. This makes every shift O(1), so the whole scan becomes O(n).
Problem Maximum Sum Subarray of Size K. Maintain the sum of the current length-k window and update the best answer after each shift.
// Fixed-size window — Maximum Sum Subarray of Size K
function maxSumSubarray(nums, k) {
let windowSum = 0, maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
windowSum += nums[i];
if (i >= k) windowSum -= nums[i - k];
if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Use this when the window is allowed to grow and shrink depending on a validity rule
Expand the right pointer until the condition breaks, then shrink from the left until the window becomes valid again. This is the main framework behind many substring and subarray interview problems.
Problem Longest Substring with At Most K Distinct Characters. Expand right, track character counts, and shrink whenever distinct characters exceed k.
// Variable-size window — Longest Substring with At Most K Distinct Chars
function longestSubstringKDistinct(s, k) {
const freq = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);
while (freq.size > k) {
const ch = s[left++];
freq.set(ch, freq.get(ch) - 1);
if (freq.get(ch) === 0) freq.delete(ch);
}
best = Math.max(best, right - left + 1);
}
return best;
}Use this as the thinking step before coding
The hardest part of sliding window is not the code but deciding exactly what makes the current window valid or invalid. Once that rule is precise, the pointer movement becomes straightforward.
Problem Minimum Window Substring. A window is valid only when it contains every required character with the needed frequency.
// Window validity — Minimum Window Substring
function minWindow(s, t) {
const need = new Map();
for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
const window = new Map();
let left = 0, formed = 0, required = need.size;
let ans = [Infinity, 0, 0];
for (let right = 0; right < s.length; right++) {
const ch = s[right];
window.set(ch, (window.get(ch) ?? 0) + 1);
if (need.has(ch) && window.get(ch) === need.get(ch)) formed++;
while (formed === required) {
if (right - left + 1 < ans[0]) ans = [right - left + 1, left, right];
const lc = s[left++];
window.set(lc, window.get(lc) - 1);
if (need.has(lc) && window.get(lc) < need.get(lc)) formed--;
}
}
return ans[0] === Infinity ? '' : s.slice(ans[1], ans[2] + 1);
}Use this when the target pattern has its own character requirements, such as in anagram or minimum window problems
One map stores what you need, and the other stores what the current window has. Comparing them incrementally is much faster than checking the whole window each time.
Problem Minimum Window Substring. Increase formed only when a character count in the window reaches the exact needed count.
// Need map vs window map — Find All Anagrams in a String
function findAnagrams(s, p) {
const need = new Map(), window = new Map();
for (const ch of p) need.set(ch, (need.get(ch) ?? 0) + 1);
let left = 0, formed = 0, required = need.size;
const result = [];
for (let right = 0; right < s.length; right++) {
const ch = s[right];
window.set(ch, (window.get(ch) ?? 0) + 1);
if (need.has(ch) && window.get(ch) === need.get(ch)) formed++;
if (right - left + 1 === p.length) {
if (formed === required) result.push(left);
const lc = s[left++];
if (need.has(lc) && window.get(lc) === need.get(lc)) formed--;
window.set(lc, window.get(lc) - 1);
if (window.get(lc) === 0) window.delete(lc);
}
}
return result;
}Use this when the problem asks for the longest, shortest, or count of valid windows
Some problems update the answer after expanding, while others update only after the window becomes valid. Knowing that timing is essential for correctness.
Problem Minimum Window Substring. Update the best answer inside the loop only while the window is valid and before shrinking it further.
// Update answer timing — Longest Substring Without Repeating Characters
function lengthOfLongestSubstring(s) {
const seen = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
if (seen.has(ch) && seen.get(ch) >= left) left = seen.get(ch) + 1;
seen.set(ch, right);
best = Math.max(best, right - left + 1); // update AFTER window is valid
}
return best;
}Use this because many hard-looking problems reduce to counting or maximizing windows with at most k distinct values, at most k zeros, or at most k replacements
Once you master this template, many interview questions become small variations.
Problem Longest Repeating Character Replacement. Track the most frequent letter in the window, and shrink when replacements needed exceed k.
// At most K template — Longest Repeating Character Replacement
function characterReplacement(s, k) {
const freq = new Map();
let left = 0, best = 0, maxFreq = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
freq.set(ch, (freq.get(ch) ?? 0) + 1);
maxFreq = Math.max(maxFreq, freq.get(ch));
while (right - left + 1 - maxFreq > k) {
const lc = s[left++];
freq.set(lc, freq.get(lc) - 1);
}
best = Math.max(best, right - left + 1);
}
return best;
}