Sliding Window

The sliding window technique is one of the most important patterns in coding interviews. It allows you to efficiently process contiguous subarrays or substrings by reusing previous computation instead of recalculating everything from scratch.

If you’ve ever written a nested loop that checks every possible subarray and felt uneasy about the O(n²) runtime — sliding window is often the optimization you’re looking for.

---

When to Think “Sliding Window”

You should immediately consider sliding window when a problem has all or most of the following traits:

• You’re working with a linear data structure
  • Array
  • String
• The problem asks about a contiguous range
  • Subarray
  • Substring
• You’re asked for:
  • Maximum / minimum
  • Longest / shortest
  • Count of valid windows
• A brute-force solution would check all subarrays or substrings

Common interview phrases that hint at sliding window:

• “Longest substring…”
• “Maximum sum of subarray of size k”
• “Smallest window containing…”
• “At most / at least k distinct characters”

---

Core Idea (Mental Model)

Think of a window defined by two pointers:

• The window represents the current contiguous range
• You expand the window by moving right
• You shrink the window by moving left
• You maintain some state about the window:
  • Sum
  • Frequency map
  • Count of distinct elements
  • Number of violations of a constraint

The key insight:

Each element enters and leaves the window at most once, giving you O(n) time.

---

Two Types of Sliding Window

1. Fixed-Size Sliding Window

The window size is constant.

Pattern

• Expand right
• Once window size exceeds k, move left
• Update answer at each valid window

Example Problem

Maximum sum of a subarray of size k

Pseudocode

windowSum = 0
left = 0

for right in range(0, n):
    windowSum += arr[right]

    if right - left + 1 == k:
        update answer using windowSum
        windowSum -= arr[left]
        left += 1

Why it works

• You reuse the previous window sum
• You add one element, remove one element
• No redundant computation

Time Complexity: O(n)

Space Complexity: O(1)

---

2. Variable-Size Sliding Window

The window size changes dynamically based on constraints.

This is more common — and more challenging — in interviews.

Pattern

1. Expand right to include new elements
2. Update window state
3. While the window is invalid, shrink from the left
4. Update answer when the window is valid

---

Canonical Variable Window Template

This template shows up again and again in interviews:

left = 0
for right in range(0, n):
    include arr[right] in window state

    while window is invalid:
        remove arr[left] from window state
        left += 1

    update answer using (left, right)

If you memorize one thing about sliding window, memorize this.

---

Example: Longest Substring Without Repeating Characters

Problem

Given a string s, find the length of the longest substring without repeating characters.

Key Observations

• Substring → contiguous
• Constraint → no duplicates
• Want longest → maximize window size

Window State

• Hash map or set of characters in the window

High-Level Logic

• Expand right
• If a character repeats, shrink from left until valid
• Track the maximum window length

Pseudocode

seen = set()
left = 0
maxLen = 0

for right in range(0, len(s)):
    while s[right] in seen:
        remove s[left] from seen
        left += 1

    add s[right] to seen
    maxLen = max(maxLen, right - left + 1)

Time Complexity: O(n)

Each character is added and removed once.

---

Common Mistakes (Interview Traps)

❌ Forgetting “Contiguous”

Sliding window only works for contiguous ranges.

If the problem allows skipping elements → this is not sliding window.

---

❌ Updating the Answer at the Wrong Time

• Fixed-size window → update when window size == k
• Variable-size window → update only when window is valid

---

❌ Incorrect Shrinking Logic

Many bugs come from:

• Shrinking too early
• Not fully restoring validity before updating the answer

Always ask:

“Is my window valid right now?”

---

Final Takeaway

Sliding window turns brute force into linear time by reusing work.

If a problem involves:

• Arrays or strings
• Contiguous ranges
• Optimization over subarrays

Your first question should be:

“Can I solve this with a sliding window?”

If you want, next we can:

• Add practice problems by difficulty
• Create a cheat sheet for window templates
• Map sliding window problems to LeetCode patterns

Just tell me how you want to extend this lesson.