A lot of array and string problems ask about a contiguous piece of the input: the longest substring without repeated characters, the shortest subarray whose sum reaches a target, the best run of k consecutive days. Checking every start and end pair is O(n²) windows, often with more work inside each. A sliding window gets it down to one pass by reusing the work from the previous window instead of starting over.
The mechanics are two indices, left and right, marking the current window. What makes the technique click, though, is deciding up front what it means for a window to be valid, and treating that rule as an invariant the loop maintains. The code here is JavaScript on Node 22.
A fixed-size window first
The simplest case has a fixed width. Find the largest sum of any 3 consecutive values in [4, 2, -1, 7, 3, -5, 6, 1]. Recomputing each window’s sum from scratch costs k additions per window. Sliding it costs two operations: add the value that enters on the right, subtract the one that leaves on the left.
function maxSumOfK(nums, k) {
let sum = 0;
for (let i = 0; i < k; i++) sum += nums[i];
let best = sum;
for (let right = k; right < nums.length; right++) {
sum += nums[right] - nums[right - k]; // one value enters, one leaves
best = Math.max(best, sum);
}
return best;
}
console.log(maxSumOfK([4, 2, -1, 7, 3, -5, 6, 1], 3));9That’s -1 + 7 + 3. Time is O(n) regardless of k, and extra space is O(1). Negative numbers are fine here, because the window’s size, not its contents, decides when to slide.
Variable windows: state the rule, then enforce it
Most interview problems have a window that grows and shrinks. Longest Substring Without Repeating Characters is the standard example. The validity rule is: no character appears more than once in the window.
With the rule written down, the loop has an obvious shape. Move right forward to add a character. If that broke the rule, move left forward, removing characters, until the rule holds again. Now the window is valid, so it’s a candidate answer.
function lengthOfLongestSubstring(s) {
const count = new Map(); // characters in the window -> occurrences
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
count.set(ch, (count.get(ch) ?? 0) + 1);
while (count.get(ch) > 1) { // the new character broke the rule: shrink
const out = s[left];
count.set(out, count.get(out) - 1);
left++;
}
best = Math.max(best, right - left + 1); // window is valid here
}
return best;
}The shrink condition only checks ch, the character that just entered. That’s safe because the window was valid before this step, so the only character that can now appear twice is the new one. Logging the window after each step on "abcabcbb":
right=0 'a' window="a" best=1
right=1 'b' window="ab" best=2
right=2 'c' window="abc" best=3
right=3 'a' window="bca" best=3
right=4 'b' window="cab" best=3
right=5 'c' window="abc" best=3
right=6 'b' window="cb" best=3
right=7 'b' window="b" best=3
3At right=3 the second a enters, the shrink loop drops the first a, and the window becomes "bca". At right=6 the incoming b forces two removals (a and the earlier b) before the window is valid again. Other inputs: "pwwkew" gives 3 ("wke"), "bbbbb" gives 1, the empty string gives 0, and "abba" gives 2.
Why the nested loop is linear
The while inside the for looks quadratic, so be ready to explain why it isn’t. right moves forward n times. left also only ever moves forward, and it can’t pass right, so across the whole run it moves at most n times. Total pointer moves: at most 2n. Each move does O(1) map work, so the algorithm is O(n) time. Space is O(m), where m is the number of distinct characters that can appear (at most the alphabet size).
The “abba” trap with last-seen indexes
A popular variant stores each character’s last index and jumps left directly past the duplicate instead of shrinking one step at a time. It’s faster in practice but has a trap:
if (lastSeen.has(ch)) {
left = lastSeen.get(ch) + 1; // buggy
// left = Math.max(left, lastSeen.get(ch) + 1); // correct
}abba without max: 3 with max: 2On "abba", when the final a arrives, its last index is 0, so the buggy line moves left backwards from 2 to 1, resurrecting a window "bba" that contains a duplicate b. The last-seen entry is stale: that a already left the window. Math.max keeps left from ever moving backwards, which is the invariant both pointers must respect.
Longest versus shortest: where you record the answer
The template changes slightly depending on whether you want the longest or shortest valid window.
- Longest valid window: shrink until the window is valid, then record. That’s the pattern above.
- Shortest valid window: record while the window is valid, shrinking to see if a smaller one still works. You stop shrinking when it becomes invalid.
Minimum Window Substring is the hard version of the second pattern. The practice problem below is the gentle one.
The validity rule can also be a formula over counts rather than a simple “no duplicates” check. In Longest Repeating Character Replacement, you can change up to k characters, and a window is valid if windowLength - countOfMostFrequentChar <= k: everything except the most common letter has to be replaced, and you’re allowed k replacements.
function characterReplacement(s, k) {
const count = new Map();
let left = 0, maxFreq = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
count.set(ch, (count.get(ch) ?? 0) + 1);
maxFreq = Math.max(maxFreq, count.get(ch));
while (right - left + 1 - maxFreq > k) { // more than k cells need changing
count.set(s[left], count.get(s[left]) - 1);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}4 4 4 2Those are "ABAB" with k=2, "AABABBA" with k=1, "AAAA" with k=0 and "ABCDE" with k=1. A subtle detail interviewers sometimes ask about: maxFreq is never decreased when the window shrinks, so it can overstate the current window’s top count. That’s harmless, because best only grows when a window beats the previous best, which requires a genuinely higher maxFreq.
Interview practice: shortest subarray with a large enough sum
Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is at least the target, or 0 if none exists. For [2, 3, 1, 2, 4, 3] and target 7, the answer is 2 ([4, 3]). Then explain what goes wrong if the array may contain negative numbers.
Answer
The validity rule is sum >= target. Because we want the shortest valid window, record the length whenever the window is valid and then shrink from the left to see whether a shorter one still qualifies:
function minSubArrayLen(target, nums) {
let left = 0, sum = 0, best = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) { // valid: record, then try to shrink
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return best === Infinity ? 0 : best;
}
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]), minSubArrayLen(4, [1, 4, 4]),
minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]));2 1 0Each pointer moves forward at most n times, so it’s O(n) time and O(1) space. The last case returns 0 because the whole array sums to 8.
The correctness argument leans on positivity. Adding an element always increases the sum, so once a window is valid, extending it further right can only make it longer, never better. Removing an element always decreases the sum, so if the window becomes invalid after shrinking, no shorter window ending at right can be valid either. Both decisions are safe only because the sum moves in one direction as the window changes.
With negatives, that breaks. Comparing the window against a brute-force check on [1, -5, 4, 3] with target 6:
negatives, window: 0 brute force: 2The right answer is [4, 3]. The window never finds it: the running sum climbs to only 3 because the -5 drags it down, the window never becomes valid, so the shrink loop never runs and never drops the unhelpful [1, -5] prefix. The fix for signed values is a different tool. Prefix sums with a monotonic deque solve this exact problem in O(n) (it’s LeetCode 862), and when the question asks for an exact sum, prefix sums with a hash map do it, as the prefix sums note shows. Recognising that a sliding window needs this one-directional behaviour, and saying so before you code, is what the second half of the question is testing.