Leetcode/Guide/Sliding Window

Contents

The Sliding Window technique is one of the most useful patterns in coding interviews.
It helps you efficiently work with subarrays or substrings — typically when you’re looking for a range that meets a certain condition (like maximum sum, minimum length, or unique characters).

Instead of recalculating every possible subarray (which is slow, O(n²)), we reuse partial results by moving the window — hence the name “sliding window.”

---

🧠 Core Idea

• Use two pointers:
  windowStart and windowEnd to represent the current window (a range within the array or string).
• Move windowEnd forward each iteration to expand the window.
• Adjust windowStart to shrink the window when a condition is met or broken.

This pattern often uses for + while loops.

---

Example 1 — Maximum Sum of Fixed-Length Subarray

Find the maximum sum of any subarray with a fixed size k.

function findMaxSumOfSubarray(numbers, subarraySize) {
  if (numbers.length < subarraySize) return null;

  let maxSum = 0;
  let currentSum = 0;

  // Calculate the sum of the first window
  for (let i = 0; i < subarraySize; i++) {
    currentSum += numbers[i];
  }

  maxSum = currentSum;

  // Slide the window
  for (let windowEnd = subarraySize; windowEnd < numbers.length; windowEnd++) {
    currentSum += numbers[windowEnd] - numbers[windowEnd - subarraySize];
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

// Demo
console.log(findMaxSumOfSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (subarray [5,1,3])

✅ Why this works:
We don’t re-sum every subarray — we just adjust the sum by subtracting the element that left and adding the new one.

---

Example 2 — Smallest Subarray with Sum ≥ Target

Find the smallest contiguous subarray whose sum is at least the given target.

function findSmallestSubarrayLengthAtLeastTarget(numbers, targetSum) {
  let windowStart = 0;
  let currentSum = 0;
  let minLength = Infinity;

  for (let windowEnd = 0; windowEnd < numbers.length; windowEnd++) {
    currentSum += numbers[windowEnd];

    while (currentSum >= targetSum) {
      const windowLength = windowEnd - windowStart + 1;
      minLength = Math.min(minLength, windowLength);
      currentSum -= numbers[windowStart];
      windowStart++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
}

// Demo
console.log(findSmallestSubarrayLengthAtLeastTarget([2, 1, 5, 2, 3, 2], 7)); // 2 (subarray [5,2])

✅ Why this works:

• windowEnd expands the window to include more elements.
• windowStart shrinks it once the sum exceeds the target.
• Keeps track of the smallest valid window dynamically.

---

Example 3 — Longest Substring Without Repeating Characters

Use a sliding window with a hash map (or object) to track seen characters.

function findLongestSubstringWithoutRepeats(inputText) {
  let windowStart = 0;
  let longestLength = 0;
  const seenCharacters = {};

  for (let windowEnd = 0; windowEnd < inputText.length; windowEnd++) {
    const currentChar = inputText[windowEnd];

    if (seenCharacters[currentChar] >= windowStart) {
      windowStart = seenCharacters[currentChar] + 1;
    }

    seenCharacters[currentChar] = windowEnd;

    const currentLength = windowEnd - windowStart + 1;
    longestLength = Math.max(longestLength, currentLength);
  }

  return longestLength;
}

// Demo
console.log(findLongestSubstringWithoutRepeats("abcabcbb")); // 3 ("abc")

✅ Why this works:
The windowStart pointer jumps past duplicate characters, ensuring the window always contains unique characters.

---

Example 4 — Longest Subarray with Ones After Replacement

Find the longest subarray containing only 1’s if you can replace at most k 0’s.

function findLongestOnesAfterReplacement(numbers, maxReplacements) {
  let windowStart = 0;
  let maxLength = 0;
  let maxOnesCount = 0;

  for (let windowEnd = 0; windowEnd < numbers.length; windowEnd++) {
    if (numbers[windowEnd] === 1) {
      maxOnesCount++;
    }

    // Current window size is larger than allowed replacements
    while ((windowEnd - windowStart + 1) - maxOnesCount > maxReplacements) {
      if (numbers[windowStart] === 1) {
        maxOnesCount--;
      }
      windowStart++;
    }

    maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
  }

  return maxLength;
}

// Demo
console.log(findLongestOnesAfterReplacement([0, 1, 1, 0, 0, 1, 1, 0], 2)); // 6

✅ Why this works:
The window grows until the number of zeros exceeds the replacement limit, then shrinks just enough to make it valid again.

---

🧩 Summary Table

---

🚀 Key Takeaways

• Two pointers define the window: windowStart, windowEnd.
• Use for to expand, while to shrink dynamically.
• Avoid recomputation — reuse sums or state.
• Common in array, string, and stream problems.
• Typical complexity: O(n) time, O(1) or O(k) space.