Sliding Window

The Sliding Window pattern is a powerful optimization technique that converts

nested loops intolinear scans. We use it to maintain a “window” that slides over a linear data structure—like an array or string—tracking a subset of elements that satisfy specific criteria.

Real-World Analogy

Imagine you are looking through a magnifying glass at a long sentence on a page.

• If the magnifying glass shows exactly 3 words at a time, you have a Fixed Window.
• As you move your hand across the page, a new word enters from the right while an old word disappears on the left.
• You don’t have to re-read the entire sentence from the start for every new word; you simply update your understanding based on what just appeared and what just left your view.

Alternatively, think of a moving train where passengers enter through the front door and exit through the back. The “state” of the train (the passenger count) changes constantly, but the train itself moves forward one stop at a time.

Visual Explanation

Let’s visualize a Variable Size Sliding Window finding the smallest subarray with a sum ≥ 7 in the array [2, 3, 1, 2, 4, 3].

  graph TD
    subgraph Step1 [1. Expand Right]
        A1["[2, 3, 1, 2], 4, 3"]
        P1["Sum: 8 (>= 7)"]
    end

    subgraph Step2 [2. Shrink Left]
        A2["2, [3, 1, 2, 4], 3"]
        P2["Sum: 10 (>= 7)"]
    end

    subgraph Step3 [3. Finding Minimum]
        A3["2, 3, 1, 2, [4, 3]"]
        P3["Sum: 7 (>= 7), Length: 2"]
    end

    Step1 --> Step2
    Step2 --> Step3

    style A3 fill:#f9d,stroke:#333

How it works:

1. Initialize: We start with two pointers, left and right, both at the beginning.
2. Expand: We move the right pointer to include more elements until our condition (e.g., sum ≥ 7) is met.
3. Shrink: Once the condition is met, we move the left pointer to see if we can make the window smaller while still satisfying the condition.
4. Tracking: At each step where the condition is met, we update our best result (like min_length).

When to Use Sliding Window

You should consider this pattern when:

• The problem asks for contiguous subarrays or substrings.
• You need to find a minimum, maximum, or optimal value (e.g., “Longest substring without repeating characters”).
• The input is a linear data structure such as an Array, String, or Linked List.
• You are currently using nested loops and want to optimize to
  O(N)
  .

Complexity Analysis

Variation	Time Complexity	Space Complexity	Explanation
Fixed Size	O(N)	O(1)	We visit each element exactly once as the window slides.
Variable Size	O(N)	O(1)	Even with a nested loop, each pointer only moves from index $0$ to $N$.
Frequency Tracking	O(N)	O(K)	$K$ is the number of unique elements (e.g., the alphabet size).

Derivation:

• Time: We often see a while loop inside a for loop, which looks like it might be $O(N^2)$. However, because the left pointer only ever moves forward and never resets, each element is added and removed from the window exactly once. This is $2 \times N$ operations, or
  O(N)
  .
• Space: Usually
  O(1)
  if we only track a sum or count. If we use a Hash Map to store character frequencies, it becomes
  O(K)
  .

Common Mistakes

1. Off-by-One Errors: Remember that the length of a window between left and right indices is right - left + 1.
2. Premature Shrinking: Moving the left pointer before you’ve recorded the valid window’s result.
3. Pointer Resetting: Never move your left pointer back to the start of the right pointer. This destroys the linear time complexity.
4. Updating Too Early: For fixed-size windows, ensure the window is fully “filled” (reaches size $K$) before you start recording results.

Next Steps

Now that you understand the theory, let’s put it into practice.

• Code Templates: Grab our “plug-and-play” templates for your favorite language.
• Practice Problems: Challenge yourself with hand-picked LeetCode problems.