DSA for Interviews, From Zero

Part 4 · Lesson 23 · 26 min read

Sliding Window: Variable Size

Grow and shrink a window to find the longest or shortest answer.

On this page

  1. When the window size is the answer
  2. The grow-and-shrink template
  3. Shortest window with a condition
  4. Traced: shortest subarray with sum ≥ 7
  5. Longest window with a condition
  6. “At most k” problems
  7. Counting windows, and “exactly k”
  8. When a sliding window works — and when it does not
  9. Practice questions (7)
  10. Make it stick
  11. What's next

When the window size is the answer

In Lesson 22 the window size k was given. Now the size is the thing you must find. Examples: the longest substring without repeated letters, or the shortest subarray with a sum of at least 7. (A substring is a block of letters in a row, and a subarray is a block of array items in a row.) Trying every start and every end costs O(n²). A variable-size window is a window that can grow and shrink. It finds the answer in O(n). It uses two pointers, l (left) and r (right), and they only move forward.

The grow-and-shrink template

Move r one step at a time to grow the window. Sometimes the window breaks the rule of the problem. When that happens, move l forward to shrink the window, until it follows the rule again. Now the window l..r is valid, and you can use it.

JavaScript
let l = 0;for (let r = 0; r < n; r++) {  add(nums[r]);                 // 1. grow: take one more item on the right  while (windowIsInvalid()) {   // 2. shrink: drop items on the left until valid again    remove(nums[l]);    l++;  }  best = Math.max(best, r - l + 1);   // 3. the window l..r is valid: use it}

It looks like a loop inside a loop, but l never moves backwards. Over the whole run, r moves n times and l moves at most n times. That is at most 2n steps in total, so the time is O(n).

Shortest window with a condition

For “shortest” problems, the logic is the other way round. Grow the window until it isgood. Then shrink it for as long as it stays good, and record its length each time.

Traced: shortest subarray with sum ≥ 7

step 1 / 26
Set up
l = 0, sum = 0, best = Infinity

No window yet. Infinity (bigger than any number) means “no valid window found yet”.

1const nums = [2, 3, 1, 2, 4, 3], target = 7;▶let l = 0, sum = 0, best = Infinity;3for (let r = 0; r < nums.length; r++) {4  sum += nums[r];5  while (sum >= target) {6    best = Math.min(best, r - l + 1);7    sum -= nums[l];8    l++;9  }10}11console.log(best);
Variables
nums[2, 3, 1, 2, 4, 3]
l0
sum0
bestInfinity
Console
(nothing printed yet)
Grow the window until the sum reaches 7. Then shrink it while the sum stays at 7 or more, and record each valid length. · interactive

Longest window with a condition

For “longest” problems, shrink the window only while it is bad. Record the length after the shrinking is done. A common example is: find the longest run of 1s if you may flip (change) at most k zeros into 1s. The rule is “at most k zeros inside the window”:

JavaScript
// Longest run of 1s if you may flip at most k zerosfunction longestOnes(nums, k) {  let l = 0, zeros = 0, best = 0;  for (let r = 0; r < nums.length; r++) {    if (nums[r] === 0) zeros++;                 // grow    while (zeros > k) {                          // invalid: too many zeros      if (nums[l] === 0) zeros--;      l++;    }    best = Math.max(best, r - l + 1);           // valid: record  }  return best;}console.log(longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2)); // 6
Shortest windowLongest window
While loop runs while…the window is validthe window is invalid
Record the answer…inside the while loopafter the while loop
Start best at…Infinity (then check if still Infinity)0

“At most k” problems

Many problems have the form “the longest window with at most k of something”. The something can be zeros, distinct (different) values, or replaced characters. The window state is a count or a frequency map (a Map that stores how many times each value appears). The rule is “that count must be ≤ k”.

JavaScript
// Longest subarray with at most k distinct valuesfunction longestAtMostK(nums, k) {  const freq = new Map();  let l = 0, best = 0;  for (let r = 0; r < nums.length; r++) {    freq.set(nums[r], (freq.get(nums[r]) ?? 0) + 1);    while (freq.size > k) {      freq.set(nums[l], freq.get(nums[l]) - 1);      if (freq.get(nums[l]) === 0) freq.delete(nums[l]);      l++;    }    best = Math.max(best, r - l + 1);  }  return best;}console.log(longestAtMostK([1, 2, 1, 2, 3, 3, 3], 2)); // 4   ([1, 2, 1, 2] or [2, 3, 3, 3])

Counting windows, and “exactly k”

Sometimes you must count the valid subarrays, not find the longest one. Look at this fact. If l..r is valid and the rule is “at most”, then every shorter window that ends at r is valid too. There are r − l + 1 of them. So add r − l + 1 to the count at each step.

“Exactly k” is harder to do with one window. When you add an item, the window can become invalid and then valid again, so the shrink rule does not work. Use this trick instead: exactly k = at most k − at most (k − 1). “At most k” counts the windows that have k or fewer different values. “At most k − 1” counts the windows that have fewer than k. So the difference leaves only the windows with exactly k.

JavaScript
// How many subarrays have at most k distinct values?function countAtMostK(nums, k) {  const freq = new Map();  let l = 0, count = 0;  for (let r = 0; r < nums.length; r++) {    freq.set(nums[r], (freq.get(nums[r]) ?? 0) + 1);    while (freq.size > k) {      freq.set(nums[l], freq.get(nums[l]) - 1);      if (freq.get(nums[l]) === 0) freq.delete(nums[l]);      l++;    }    count += r - l + 1;          // every window ending at r and starting in l..r is valid  }  return count;}// exactly k = (at most k) − (at most k − 1)const exactly = (nums, k) => countAtMostK(nums, k) - countAtMostK(nums, k - 1);console.log(exactly([1, 2, 1, 2, 3], 2)); // 7

When a sliding window works — and when it does not

A window works only when shrinking always helps in the same direction. For sums, this needs non-negative values (zero or bigger). Removing an item must never make the sum bigger. With negative numbers, a longer window can have a smaller sum. Then the grow-and-shrink logic gives wrong answers.

Negative numbers → use prefix sums instead

Suppose you must “count the subarrays with a sum of exactly k”, and the array may have negative values. A sliding window cannot solve this. Use prefix sums with a Map (Lesson 20) instead.

Dry run · choosing a technique for subarray problems
Problem shapeValuesTechnique
Every block of exactly k itemsanyFixed window (Lesson 22)
Longest / shortest with a rule that shrinking fixesnon-negative, or countsVariable window
Count of subarrays with sum = kmay be negativePrefix sum + Map (Lesson 20)
Largest sum of any subarrayanyKadane (Lesson 24)

Practice questions

For each question, decide two things. Is it a “longest”, “shortest” or “count” question? What rule makes a window valid?

Q1Minimum size subarray sumMedium

Return the length of the shortest subarray whose sum is at least target. If there is none, return 0. All values are positive.

Example 1
Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: [4, 3] is the shortest subarray with sum ≥ 7.
Example 2
Input: target = 4, nums = [1, 4, 4]
Output: 1
Explanation: [4] alone is enough.
Example 3
Input: target = 11, nums = [1, 1, 1, 1, 1]
Output: 0
Explanation: Even the whole array sums to only 5.
Stuck? Open one hint at a time
Hint 1
All values are positive, so shrinking the window always lowers the sum.
Hint 2
Use the shortest-window template: shrink the window while the sum is still ≥ target.
Show the solution with explanations
Approach 1Grow and shrink
The idea

This is the algorithm we traced. Return 0 if no window was ever valid.

JavaScript
function minSubArrayLen(target, nums) {  let l = 0, sum = 0, best = Infinity;  for (let r = 0; r < nums.length; r++) {    sum += nums[r];    while (sum >= target) {      best = Math.min(best, r - l + 1);      sum -= nums[l++];    }  }  return best === Infinity ? 0 : best;}console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]));  // 2console.log(minSubArrayLen(4, [1, 4, 4]));           // 1console.log(minSubArrayLen(11, [1, 1, 1, 1, 1]));    // 0
How it works

O(n) time, O(1) space. The last line changes “never found” (Infinity) into the 0 that the question asks for.

Which approach should you use?

There is also a solution with prefix sums and binary search. It takes O(n log n). The window is simpler and faster. (LeetCode 209.)

Q2Longest substring without repeating charactersMedium

Return the length of the longest substring of s that has no repeated characters.

Example 1
Input: "abcabcbb"
Output: 3
Explanation: "abc".
Example 2
Input: "bbbbb"
Output: 1
Explanation: "b".
Example 3
Input: "pwwkew"
Output: 3
Explanation: "wke". ("pwke" is a subsequence, not a substring, because its letters are not next to each other.)
Stuck? Open one hint at a time
Hint 1
The rule is: no character appears twice in the window.
Hint 2
When the new character is already in the window, shrink the window from the left until it is not.
Show all 2 solutions with explanations
Approach 1Window with a Set
The idea

Grow the window with r. While s[r] is already in the Set, remove s[l] and move l forward.

JavaScript
function lengthOfLongestSubstring(s) {  const inWindow = new Set();  let l = 0, best = 0;  for (let r = 0; r < s.length; r++) {    while (inWindow.has(s[r])) {      inWindow.delete(s[l]);      l++;    }    inWindow.add(s[r]);    best = Math.max(best, r - l + 1);  }  return best;}console.log(lengthOfLongestSubstring("abcabcbb")); // 3console.log(lengthOfLongestSubstring("bbbbb"));    // 1console.log(lengthOfLongestSubstring("pwwkew"));   // 3
How it works

O(n). Each character is added once and removed at most once.

Approach 2Jump l with last positions
The idea

Remember the last index of each character. When a character repeats, jump l to just after the earlier copy. You do not shrink step by step.

JavaScript
function lengthOfLongestSubstring(s) {  const last = new Map();  let l = 0, best = 0;  for (let r = 0; r < s.length; r++) {    if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1;    last.set(s[r], r);    best = Math.max(best, r - l + 1);  }  return best;}console.log(lengthOfLongestSubstring("abcabcbb")); // 3console.log(lengthOfLongestSubstring("pwwkew"));   // 3
How it works

It is still O(n), but with fewer steps. The check >= l ignores old copies that are already outside the window.

Which approach should you use?

This is one of the most asked interview questions. Lesson 31 comes back to it with other string windows. (LeetCode 3.)

Q3Max consecutive ones IIIMedium

Return the longest run of 1s you can get if you flip at most k zeros to 1.

Example 1
Input: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Explanation: Flip the zeros at indices 5 and 10 to 1. Then indices 5–10 are six 1s in a row.
Example 2
Input: nums = [0, 0, 1, 1], k = 0
Output: 2
Explanation: No flips are allowed, so the longest run is the two 1s.
Stuck? Open one hint at a time
Hint 1
Say it in other words: find the longest window that has at most k zeros.
Show the solution with explanations
Approach 1Longest window with ≤ k zeros
The idea

Count the zeros in the window. Shrink the window while it has more than k zeros.

JavaScript
function longestOnes(nums, k) {  let l = 0, zeros = 0, best = 0;  for (let r = 0; r < nums.length; r++) {    if (nums[r] === 0) zeros++;    while (zeros > k) {      if (nums[l] === 0) zeros--;      l++;    }    best = Math.max(best, r - l + 1);  }  return best;}console.log(longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2)); // 6console.log(longestOnes([0, 0, 1, 1], 0));                      // 2
How it works

O(n) time, O(1) space. The question says “flip”, but the code never flips anything. The real step is to say the problem again as a window rule.

Which approach should you use?

If you say “at most k changes” as “at most k bad items in the window”, you can solve a whole group of problems. (LeetCode 1004.)

Q4Fruit into basketsMedium

Trees stand in a row, and tree i gives fruit of type fruits[i]. You have two baskets, and each basket holds only one type of fruit. You start at any tree and move to the right. You must pick one fruit from every tree, until you meet a fruit that fits in neither basket. Return the most fruit you can pick.

Example 1
Input: [1, 2, 1]
Output: 3
Explanation: Two types, all three trees.
Example 2
Input: [0, 1, 2, 2]
Output: 3
Explanation: [1, 2, 2].
Example 3
Input: [1, 2, 3, 2, 2]
Output: 4
Explanation: [2, 3, 2, 2].
Stuck? Open one hint at a time
Hint 1
You have two baskets, and each holds one type. So find the longest window with at most 2 distinct (different) values.
Show the solution with explanations
Approach 1At most 2 distinct
The idea

Use the “at most k distinct” window from the lesson, with k = 2.

JavaScript
function totalFruit(fruits) {  const freq = new Map();  let l = 0, best = 0;  for (let r = 0; r < fruits.length; r++) {    freq.set(fruits[r], (freq.get(fruits[r]) ?? 0) + 1);    while (freq.size > 2) {      freq.set(fruits[l], freq.get(fruits[l]) - 1);      if (freq.get(fruits[l]) === 0) freq.delete(fruits[l]);      l++;    }    best = Math.max(best, r - l + 1);  }  return best;}console.log(totalFruit([1, 2, 1]));       // 3console.log(totalFruit([0, 1, 2, 2]));    // 3console.log(totalFruit([1, 2, 3, 2, 2])); // 4
How it works

O(n). The story about baskets hides a standard pattern. Interviewers like to wrap a pattern in a story.

Which approach should you use?

Practise turning the story into “the longest window with at most 2 distinct values”. (LeetCode 904.)

Q5Longest run of 1s after deleting one elementMedium

Delete exactly one element from a binary array (an array of 0s and 1s). Return the length of the longest run of 1s in what is left.

Example 1
Input: [1, 1, 0, 1]
Output: 3
Explanation: Delete the 0: [1, 1, 1].
Example 2
Input: [0, 1, 1, 1, 0, 1, 1, 0, 1]
Output: 5
Explanation: Delete the 0 at index 4: [1, 1, 1, 1, 1].
Example 3
Input: [1, 1, 1]
Output: 2
Explanation: Edge case: you must delete one element, even a 1.
Stuck? Open one hint at a time
Hint 1
Use a window with at most one 0. The answer is the window length minus 1, because one element is deleted.
Show the solution with explanations
Approach 1Window with ≤ 1 zero
The idea

This is the same as Question 3 with k = 1. Subtract 1 for the deleted element.

JavaScript
function longestSubarray(nums) {  let l = 0, zeros = 0, best = 0;  for (let r = 0; r < nums.length; r++) {    if (nums[r] === 0) zeros++;    while (zeros > 1) {      if (nums[l] === 0) zeros--;      l++;    }    best = Math.max(best, r - l);      // window length − 1  }  return best;}console.log(longestSubarray([1, 1, 0, 1]));                 // 3console.log(longestSubarray([0, 1, 1, 1, 0, 1, 1, 0, 1]));  // 5console.log(longestSubarray([1, 1, 1]));                    // 2
How it works

O(n). The code uses r - l instead of r - l + 1. This handles the forced deletion, including the edge case where all values are 1.

Which approach should you use?

This is a very small change from Question 3. Notice that the formula handles the edge case, so you do not need an extra if. (LeetCode 1493.)

Q6Subarrays with product less than kMedium

Count the subarrays of positive integers whose product is less than k (not equal to k).

Example 1
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Example 2
Input: nums = [1, 2, 3], k = 0
Output: 0
Explanation: No product is less than 0.
Stuck? Open one hint at a time
Hint 1
The values are positive, so a product only gets bigger as the window gets bigger.
Hint 2
For each r, add r - l + 1 to the count.
Show the solution with explanations
Approach 1Counting window
The idea

Keep the window product below k. Every window that ends at r and starts anywhere in l..r counts.

JavaScript
function numSubarrayProductLessThanK(nums, k) {  if (k <= 1) return 0;  let l = 0, product = 1, count = 0;  for (let r = 0; r < nums.length; r++) {    product *= nums[r];    while (product >= k) product /= nums[l++];    count += r - l + 1;  }  return count;}console.log(numSubarrayProductLessThanK([10, 5, 2, 6], 100)); // 8console.log(numSubarrayProductLessThanK([1, 2, 3], 0));       // 0
How it works
Dry run · [10, 5, 2, 6], k = 100
rwindowproductadded
0[10]101
1[10, 5]502
2[5, 2] (10 removed)102
3[5, 2, 6]603

1 + 2 + 2 + 3 = 8. The k ≤ 1 check prevents the while loop from shrinking past r.

Which approach should you use?

O(n) time. The step count += r - l + 1 is the key idea for counting with windows. (LeetCode 713.)

Q7Subarrays with exactly k different valuesHard

Return the number of subarrays that have exactly k different values.

Example 1
Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 7
Explanation: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2
Input: nums = [1, 2, 1, 3, 4], k = 3
Output: 3
Explanation: [1,2,1,3], [2,1,3], [1,3,4].
Stuck? Open one hint at a time
Hint 1
It is hard to count “exactly k” directly with one window.
Hint 2
Count “at most k” and “at most k − 1”. Then subtract.
Show the solution with explanations
Approach 1atMost(k) − atMost(k − 1)
The idea

Run the counting window from the lesson two times.

JavaScript
function atMost(nums, k) {  const freq = new Map();  let l = 0, count = 0;  for (let r = 0; r < nums.length; r++) {    freq.set(nums[r], (freq.get(nums[r]) ?? 0) + 1);    while (freq.size > k) {      freq.set(nums[l], freq.get(nums[l]) - 1);      if (freq.get(nums[l]) === 0) freq.delete(nums[l]);      l++;    }    count += r - l + 1;  }  return count;}function subarraysWithKDistinct(nums, k) {  return atMost(nums, k) - atMost(nums, k - 1);}console.log(subarraysWithKDistinct([1, 2, 1, 2, 3], 2)); // 7console.log(subarraysWithKDistinct([1, 2, 1, 3, 4], 3)); // 3
How it works

O(n), because it makes two passes. A subarray with exactly k distinct values is counted by atMost(k) but not by atMost(k − 1). So the subtraction leaves just those subarrays.

Which approach should you use?

This is a hard problem, but it becomes short when you know the subtraction trick. The same trick also counts “exactly k odd numbers” (LeetCode 1248) and similar problems. (LeetCode 992.)

Make it stick

Make it stick — close this page, then
  1. Write the grow-and-shrink template from memory.
  2. Explain why the template is O(n) even though it has a while loop inside a for loop.
  3. State where the answer is recorded for “longest” vs “shortest” windows.
  4. Explain the “exactly k = at most k − at most k − 1” trick.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Lesson 24 solves “the largest sum of any subarray”. Windows do not work for this problem, because the values can be negative. Instead we use Kadane's algorithm. It needs one pass and one simple choice for each item.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series