Sliding Windows That Grow and Shrink

The problem shape comes before the window

A subarray is a contiguous section of an array. A substring is a contiguous section of a string. “Contiguous” means the elements remain next to one another in their original order; you cannot skip an element in the middle.

Many questions ask for the longest, shortest, or number of contiguous regions satisfying a condition. A brute-force approach chooses every starting boundary and every ending boundary, then inspects what lies between them. That repeats a great deal of work.

For the string "abcd", the regions starting at index zero are:

a
ab
abc
abcd

The region abc contains almost all the information from ab. Recomputing its state from scratch wastes the work already done.

A window is a changing interval plus a summary

A sliding window keeps two boundaries, usually called left and right, around the current contiguous region:

a b c a b
  ↑   ↑
 left right

current window = "bca"

It also stores only the information needed to judge that region—a sum, a Set of characters, or a frequency map. When right expands the window, add one item to the summary. When left shrinks it, remove one item.

The basic rhythm is:

expand right
update state for the incoming item
shrink left when the objective requires it
record the answer at the correct moment

The difficult part is deciding what “requires it” means.

Longest valid window: shrink while invalid

Consider the longest substring with no repeated characters. A Set can describe the current window because it only needs to answer whether a character is already present.

When a new character creates a duplicate, the window is invalid. Remove characters from the left until the duplicate is gone. Use while, not if, because restoring validity may require several removals.

function lengthOfLongestSubstring(text: string): number {
  const windowCharacters = new Set<string>()
  let left = 0
  let best = 0

  for (let right = 0; right < text.length; right += 1) {
    while (windowCharacters.has(text[right])) {
      windowCharacters.delete(text[left])
      left += 1
    }

    windowCharacters.add(text[right])
    best = Math.max(best, right - left + 1)
  }

  return best
}

The window is valid when its characters are unique. The length is right - left + 1 because both boundary positions belong to the window.

Worked trace: "abba"

right  incoming  window before repair  repair             valid window  best
0      a         a                     none               a             1
1      b         ab                    none               ab            2
2      b         abb                   remove a, then b   b             2
3      a         ba                    none               ba            2

Removing only a when the second b arrives would leave bb, which is still invalid. That is why the repair is a while loop.

The invariant after the repair is:

The interval from left through right contains no repeated character, and the Set contains exactly those characters.

Only after restoring that invariant is it safe to measure a candidate longest window.

Shortest valid window: shrink while valid

Now consider an array of positive integers. Find the shortest contiguous subarray whose sum is at least a target.

The goal is different. Once the sum reaches the target, the window is valid—but it may be wider than necessary. Record its length and keep removing from the left while it remains valid. Every successful removal produces a smaller candidate.

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0
  let sum = 0
  let best = Infinity

  for (let right = 0; right < nums.length; right += 1) {
    sum += nums[right]

    while (sum >= target) {
      best = Math.min(best, right - left + 1)
      sum -= nums[left]
      left += 1
    }
  }

  return best === Infinity ? 0 : best
}

Worked trace: target 7, values [2, 3, 1, 2, 4, 3]

expand through 2,3,1,2 → sum 8, window length 4
record 4, remove left 2 → sum 6, stop shrinking

add 4 → sum 10
record length 4, remove 3 → sum 7
record length 3, remove 1 → sum 6

add 3 → sum 9
record length 3, remove 2 → sum 7
record length 2 for [4,3], remove 4 → sum 3
answer = 2

Notice that validity triggers more shrinking, not less. For a minimum problem, a valid window is an opportunity to search for a smaller valid window ending at the same right.

Why positive numbers matter

The sum algorithm relies on predictable movement:

• adding a positive number on the right cannot decrease the sum;
• removing a positive number on the left cannot increase the sum.

Negative values destroy that monotonic relationship. If the sum is too small, expanding could make it smaller. If the sum is large enough, removing a negative value could make it even larger. The pointer decisions would no longer eliminate possibilities safely.

For arbitrary positive and negative values, return to the prefix-sum reasoning from Week 2 or use another technique appropriate to the exact objective.

Why the nested loop is still linear

Both examples contain a while loop inside a for loop, which can look quadratic. Count movements instead of loop nesting:

• right advances from start to end once;
• left advances from start to end at most once;
• neither pointer moves backward.

Each element enters the window once and leaves at most once. The total work is therefore O(n). The character example uses up to O(k) space for the distinct characters in the window; the sum example uses O(1) auxiliary space.

One framework, two shrinking rules

This table is a starting point, not a replacement for reasoning. Define validity in plain language, decide how each incoming and outgoing item changes it, and prove that pointer movement is one-directional.

Checkpoint

For any proposed sliding-window solution, say:

1. what interval the window represents;
2. what state summarizes it;
3. what makes it valid or invalid;
4. why moving left is safe;
5. whether the answer is recorded before or after shrinking.

If those answers are clear, the code usually becomes a direct translation.