Algorithms - 2. Sliding Window (Variable Size)

When to use Variable-Size Sliding Window

Use variable-size sliding window when you need to find optimal contiguous subarrays where the size isn't predetermined. The algorithm dynamically adjusts window boundaries to maintain a specific condition while optimizing for size.

Minimum/maximum size subarray with sum ≥ target (classic use case)
Longest substring without repeating characters
Minimum window substring containing all required characters
Count of subarrays with specific properties
Maximum items collection with constraint on variety (e.g., fruit baskets)
Any problem where window size adapts to maintain a condition

Example problem

Minimum Grocery Bags: Given item weights [2, 3, 1, 2, 4, 3] and you need at least 7 kg total, what's the minimum number of consecutive items to pick?

Items [0-3]: 2 + 3 + 1 + 2 = 8 kg ✓ (4 items)
Items [1-4]: 3 + 1 + 2 + 4 = 10 kg ✓ (4 items)
Items [2-4]: 1 + 2 + 4 = 7 kg ✓ (3 items)
Items [4-5]: 4 + 3 = 7 kg ✓ (2 items) ← Best!

Answer: 2 items (items at positions 4-5).

Single most important insight

Expand the window to explore possibilities, then shrink from the left when the condition is satisfied - this expand-shrink dance guarantees we examine all valid windows by systematically adjusting boundaries to find the optimal size without checking all O(n²) possibilities.

Mental note: The algorithm's genius lies in maintaining a "valid window invariant". At each step, we only need to decide: "Can I shrink this window and still satisfy the condition?" This simple decision automatically finds the optimal window. Instead of checking all possible windows, we expand to include new elements, then greedily shrink to find the smallest valid window ending at each position.

Decision Framework

At every position, the algorithm makes two sequential decisions:

EXPAND: Always include the current element (move right pointer)
SHRINK: While the condition is satisfied, try to minimize by removing from left

Code

// Find minimum size subarray with sum >= target
// O(n) time despite nested loops - each element visited at most twice
function shortestSubarray(nums, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    // Step 1: EXPAND - always include current element
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // DECISION FRAMEWORK: Can we shrink and still satisfy condition?
    // Use while (not if) to find the OPTIMAL window, not just any valid window
    while (windowSum >= target) {
      // Current window satisfies condition, record if it's the smallest
      const currentWindowSize = right - left + 1;
      minLength = Math.min(minLength, currentWindowSize);

      // Try to find even smaller valid window by shrinking from left
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

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

// Longest substring with at most k distinct characters
// Problem: Find the longest substring that contains at most k different characters
// Example: "eceaba" with k=2 → "eceab" has 3 chars ✗, but "eceba" has 3 chars ✗, "ece" has 2 chars ✓
function longestSubstringKDistinct(s, k) {
  const charFrequency = new Map(); // Track count of each character in window
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    // EXPAND: Add character to window
    const charEntering = s[right];
    charFrequency.set(charEntering, (charFrequency.get(charEntering) || 0) + 1);

    // DECISION FRAMEWORK: Shrink FROM LEFT if we exceed k distinct characters
    // Why shrink from left, not right? Because:
    // 1. We're systematically trying every position as the RIGHT boundary
    // 2. For each right position, we find the LEFTMOST valid position
    // 3. This ensures we check ALL possible windows (see doubt buster below)
    while (charFrequency.size > k) {
      const charLeaving = s[left];
      const count = charFrequency.get(charLeaving);

      // Decrease frequency of the character leaving the window
      if (count === 1) {
        // This was the last occurrence, remove from map
        charFrequency.delete(charLeaving);
      } else {
        // Still more occurrences in the window
        charFrequency.set(charLeaving, count - 1);
      }
      left++;
    }

    // Window is valid here (≤ k distinct chars), update maximum
    const currentWindowSize = right - left + 1;
    maxLength = Math.max(maxLength, currentWindowSize);
  }

  return maxLength;
}

Doubt buster

Common doubt: "Why only shrink from the left? What if removing from the right would give a better result?"

Why you might think removing from right could be better

This is a natural concern! When the window has too many distinct characters, you might think:

"What if the character we just added (at right) is the problem?"
"Maybe removing from the right would keep a longer valid window?"
"Why not try both directions and pick the better one?"
"The greedy choice of always shrinking left seems arbitrary"

For example, with string "abcba" and k=2:

When we reach index 2 (character 'c'), window is "abc" with 3 distinct chars
Removing from left gives "bc" (length 2)
But what if removing from right gives "ab" (also length 2)?
Shouldn't we consider both options?

Why this thinking is wrong

Key realization: We don't need to remove from the right because we'll explore that option naturally in future iterations!

Here's the crucial insight: The algorithm systematically tries EVERY position as the right boundary. So if removing from the right would give a better window, we'll discover it when we reach that position.

Let's prove this with "abcba" and k=2:

right=0: Window ["a"], 1 distinct char, valid ✓
right=1: Window ["ab"], 2 distinct chars, valid ✓, maxLen=2
right=2: Window ["abc"], 3 distinct chars, invalid ✗
  - Shrink from left: ["bc"], 2 distinct chars, valid ✓
right=3: Window ["bcb"], 2 distinct chars, valid ✓, maxLen=3
right=4: Window ["bcba"], 3 distinct chars, invalid ✗
  - Shrink: ["cba"], 3 distinct chars, still invalid ✗
  - Shrink: ["ba"], 2 distinct chars, valid ✓

The key insight: When we had "abc" and removed from left to get "bc", you worried we missed "ab". But notice:

The window "ab" was already evaluated when right=1!
We recorded its length (2) at that time
Later, we found "bcb" with length 3, which is better

Every possible window gets evaluated because:

Windows ending at position 1: We tried ["a"], ["ab"]
Windows ending at position 2: We tried ["abc"]→["bc"], ["c"]
Windows ending at position 3: We tried ["bcb"], ["cb"], ["b"]
And so on...

The algorithm doesn't miss any window - it systematically evaluates all of them!

Concrete proof: Why shrinking from left is sufficient

Think of it this way: If there's an optimal window [i, j], the algorithm WILL find it:

When right pointer reaches j: We'll have all elements from some left position to j
The while loop shrinks: It moves left pointer rightward until the window is valid
It will stop at or before i: Because [i, j] is valid, the shrinking will stop by position i
We record this window: If it's the best seen so far, we update our maximum

Why removing from right would be redundant

Imagine we're at position right=5 with window [2,3,4,5] and it's invalid. You might think "what if [2,3,4] is better than [3,4,5]?"

But here's why we don't need to check [2,3,4]:

We already checked [2,3,4] when right was at position 4!
If [2,3,4] was valid and good, we recorded it then
Now at position 5, we're finding the best window that ENDS at 5
Next iteration (right=6), we'll find the best window ending at 6

The algorithm's guarantee: For every possible window in the array, there will be a moment when:

The right pointer is at the window's end position
The left pointer will be moved to (or past) the window's start position
Thus, every window gets evaluated exactly once

This is why the algorithm is O(n) despite seeming to need O(n²) - we never need to backtrack or reconsider previous decisions.