DSA Patterns: Sliding Window

One of the most powerful tools for working with contiguous subarrays or substrings is the Sliding Window pattern. It helps reduce brute-force O(n²) problems into clean and efficient O(n) solutions by reusing work already done in previous iterations.

Let’s break it down.

📌 When to Use Sliding Window

Use this when:

• You're dealing with subarrays or substrings
• The problem involves max/min sum, distinct characters, frequency counts, or window sizes
• You want to avoid recomputing things for each subarray

---

🧰 Sliding Window Templates

Here are two general-purpose templates you can use during interviews:

✅ Fixed-Size Window (e.g., Max Sum Subarray of Size K)

Initialize windowSum = 0
Initialize maxResult = -∞
Initialize l = 0

for r from 0 to end of array:
    Add array[r] to windowSum

    if (window size == k):
        Update maxResult using windowSum
        Subtract array[l] from windowSum
        Move l forward

✅ Variable-Size Window (e.g., Longest Substring Without Repeating Characters)

Initialize data structure to track window state
Initialize l = 0

for r from 0 to end of array:
    Expand window to include array[r]

    while (window is invalid):
        Shrink window from the left (remove array[l])
        Move l forward

    Update result if needed

• Use the fixed version when the window size is given.
• Use the variable version when you're sliding based on a condition like uniqueness, frequency, or constraints.

---

🔍 Core Idea

Instead of recalculating from scratch, maintain a "window" over part of the array/string:

• Expand the window to include new elements
• Shrink the window when a condition is violated (or to optimize)
• Track the result at each valid state

The trick is to slide the window only forward, keeping time complexity at O(n).

---

🧪 Sample Problem 1: Longest Substring Without Repeating Characters (Medium)

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

Input:

s = "abcabcbb"

Expected Output:

3  → "abc"

Why Sliding Window Works Here

• We're asked to find the longest substring, which implies a contiguous window
• The moment we see a duplicate character, the current window becomes invalid
• We can adjust the window dynamically using two pointers: l and r

Let’s walk through it step-by-step.

---

Step-by-Step ASCII Dry Run

We'll track:

• l → start of current window
• r → current character
• charSet → current unique characters in the window

Initial State:
s = "a  b  c  a  b  c  b  b"
     ↑
     l, r = 0
charSet = {}

Step 1:
Add 'a' → charSet = {'a'}
[ a ] → maxLen = 1

Step 2:
Move r = 1, add 'b' → charSet = {'a', 'b'}
[ a  b ] → maxLen = 2

Step 3:
Move r = 2, add 'c' → charSet = {'a', 'b', 'c'}
[ a  b  c ] → maxLen = 3

Step 4:
Move r = 3, duplicate 'a' found
→ Remove 'a', move l = 1
→ Now window is [ b  c  a ] → charSet = {'b', 'c', 'a'}
→ maxLen still 3

Step 5:
Move r = 4, duplicate 'b' found
→ Remove 'b', move l = 2
→ Now window is [ c  a  b ] → charSet = {'c', 'a', 'b'}
→ maxLen still 3

Step 6:
Move r = 5, duplicate 'c' found
→ Remove 'c', move l = 3
→ Now window is [ a  b  c ] → charSet = {'a', 'b', 'c'}
→ maxLen still 3

Step 7:
Move r = 6, duplicate 'b' found
→ Remove 'a', move l = 4
→ Remove 'b', move l = 5
→ Now window = [ c  b ] → charSet = {'c', 'b'}
→ maxLen still 3

Step 8:
Move r = 7, duplicate 'b' found
→ Remove 'c', move l = 6
→ Remove 'b', move l = 7
→ Now window = [ b ] → charSet = {'b'}
→ maxLen still 3

Final maxLen = 3 ("abc")

---

⏱ Time & Space Complexity

• Time: O(n), each character visited at most twice
• Space: O(k), where k is number of unique chars in window (e.g., 26 for lowercase)

---

🧠 Why This Works

This is a textbook case for sliding window:

• The "longest valid window" expands until invalid
• When a constraint is violated (duplicate found), we shrink from the left
• We never go backward → O(n) time

We turn nested loops into a single pass.

---

🧪 Sample Problem 2: Maximum Sum Subarray of Size K

🧠 Intuition

In this problem, you’re given an array of integers and a number k, and you need to find the maximum sum of any subarray of size k.

---

❌ Brute Force Approach (Why It Fails)

• Loop over every possible subarray of size k
• For each, compute the sum from scratch
• Time complexity: O(n × k) — not efficient for large arrays

---

✅ Sliding Window Insight

If we slide a fixed-size window across the array:

• We add the new incoming element
• We remove the outgoing element from the left
• And just update the running sum instead of recalculating it

This makes it O(n) time — a huge improvement.

---

🧪 Problem

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Expected Output: 9  → subarray [5, 1, 3]

---

Step-by-Step ASCII Dry Run (Using l and r)

We'll track:

• l = left of the window
• r = right of the window
• windowSum = current running sum of the window
• maxSum = max sum seen so far

### 🧪 Dry Run: Max Sum Subarray of Size K  
Input: nums = [2, 1, 5, 1, 3, 2], k = 3  
Expected Output: 9 → subarray [5, 1, 3]

Initial State  
l = 0, r = 0, windowSum = 0, maxSum = 0

Step 1: r = 0  
Add 2 → windowSum = 2  
Window: [2] → Not full yet  
maxSum = 0

Step 2: r = 1  
Add 1 → windowSum = 3  
Window: [2, 1] → Not full yet  
maxSum = 0

Step 3: r = 2  
Add 5 → windowSum = 8  
Window: [2, 1, 5] → Full window  
Update maxSum = 8

Step 4: r = 3  
Add 1 → windowSum = 9  
Remove nums[l] = 2 → windowSum = 7  
Move l = 1  
Window: [1, 5, 1]  
maxSum = 8

Step 5: r = 4  
Add 3 → windowSum = 10  
Remove nums[l] = 1 → windowSum = 9  
Move l = 2  
Window: [5, 1, 3]  
Update maxSum = 9

Step 6: r = 5  
Add 2 → windowSum = 11  
Remove nums[l] = 5 → windowSum = 6  
Move l = 3  
Window: [1, 3, 2]  
maxSum = 9

Final Answer:  
maxSum = 9 → subarray [5, 1, 3]

---

⏱ Time & Space Complexity

• Time: O(n) — each element is added and removed once
• Space: O(1) — just numbers, no extra structures

---

✅ Why This Works

• We're keeping a fixed-length window over the array

• Instead of recalculating from scratch, we reuse the sum by:

  • Adding new item
  • Subtracting the one that fell out of the window
• This gives us linear time — and is exactly what the sliding window is best at

---

🧪 Sample Problem 3: Best Time to Buy and Sell Stock

Problem:
You're given an array where each element represents the stock price on that day.
Find the maximum profit you can make by buying on one day and selling on a later day.

Input:

prices = [7, 1, 5, 3, 6, 4]

Expected Output:

5 (Buy at 1, Sell at 6)

This may not look like a sliding window problem at first, but it is — just not with a fixed window size.
Here’s how we frame it:

• Think of the l pointer as the day we choose to buy (left of the window)
• The r pointer moves forward, scanning every potential sell day
• We calculate profit as prices[r] - prices[l]
• If we ever find a cheaper buy price (i.e., prices[r] < prices[l]), we update l
• The goal is to keep updating maxProfit with the best opportunity so far

Initial State:
l = 0, r = 1, maxProfit = 0

Step 1: r = 1  
prices[r] = 1 < prices[l] = 7  
→ Update l = 1 (cheaper buy day)  
→ maxProfit stays 0

Step 2: r = 2  
prices[r] = 5 > prices[l] = 1  
→ Profit = 5 - 1 = 4 → Update maxProfit = 4

Step 3: r = 3  
prices[r] = 3 > prices[l] = 1  
→ Profit = 3 - 1 = 2 → maxProfit stays 4

Step 4: r = 4  
prices[r] = 6 > prices[l] = 1  
→ Profit = 6 - 1 = 5 → Update maxProfit = 5

Step 5: r = 5  
prices[r] = 4 > prices[l] = 1  
→ Profit = 4 - 1 = 3 → maxProfit stays 5

Final Answer:  
maxProfit = 5

✅ This solution works in O(n) time with two pointers, no extra space.
We dynamically adjust our “buy day” and use the current price as a “sell day” to check the best opportunity at each step.

---

✅ Final Summary: When to Use Sliding Window

Sliding Window is your go-to pattern when:

• You're working with contiguous ranges
• You need to optimize or satisfy a constraint
• You want to avoid recomputing from scratch

Master these:

• Longest Substring Without Repeating Characters
• Max Sum Subarray of Size K
• Best Time to Buy and Sell Stock
• Minimum Window Substring
• Longest Repeating Character Replacement
• Permutation in String