DSA: Topic 4: Sliding Window

Interview frequency: ⭐⭐⭐⭐⭐

Many candidates confuse Two Pointers and Sliding Window.

The difference is:

• Two Pointers: Usually solving pair/comparison problems.
• Sliding Window: Solving subarray or substring problems.

If you master Sliding Window, you can solve dozens of interview questions.

---

When should you think "Sliding Window"?

Whenever you see words like:

• Longest...
• Shortest...
• Maximum...
• Minimum...
• Continuous
• Contiguous
• Subarray
• Substring

For example:

Find the longest substring without repeating characters.

Maximum sum of a subarray of size k.

Smallest subarray with sum ≥ k.

These are classic sliding window problems.

---

What is a Sliding Window?

Imagine a window moving across the array.

Example:

Array: [2, 1, 5, 1, 3, 2]

Window size = 3

[2,1,5] 1 3 2
 2 [1,5,1] 3 2
 2 1 [5,1,3] 2
 2 1 5 [1,3,2]

Instead of recalculating every window from scratch, update the window efficiently.

---

Problem 1: Maximum Sum Subarray of Size K

Example

nums = [2,1,5,1,3,2]
k = 3

Windows:

2+1+5 = 8

1+5+1 = 7

5+1+3 = 9

1+3+2 = 6

Answer:

9

---

Brute Force

For every position:

• Compute the sum again.

Time = O(n × k)

Too slow for large inputs.

---

Optimised Sliding Window

Step 1

Compute the first window.

window_sum = sum(nums[:k])
max_sum = window_sum

Current window:

[2,1,5]

Sum = 8

---

Step 2

Move one step.

Instead of adding everything again,

Subtract the element leaving the window.

Add the new element entering.

Old window

2 1 5

↓

Remove 2

Add 1

↓

1 5 1

Formula:

window_sum = window_sum - nums[left] + nums[right]

Complete solution:

def max_sum(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right-k]

        max_sum = max(max_sum, window_sum)

    return max_sum

Complexity

Time : O(n)

Space: O(1)

---

Fixed vs Variable Sliding Window

There are two types.

1. Fixed Window

Size never changes.

Example:

Window size = 4

Questions:

• Maximum sum of size k
• Average of size k
• First negative number in every window

---

2. Variable Window

Window expands and shrinks.

Example:

Longest substring without repeating characters

Here the size changes dynamically.

---

Variable Window Example

Longest Substring Without Repeating Characters

Input

abcabcbb

Start:

[a]

Expand:

[a b]

Expand:

[a b c]

Next character:

a

Already exists.

Now shrink from the left until the duplicate is removed.

Continue expanding.

This "expand → shrink → expand" idea is the heart of variable sliding windows.

---

Generic Sliding Window Template

left = 0

for right in range(len(nums)):

    # Expand window

    while window_is_invalid:
        # Shrink window
        left += 1

    # Update answer

This template solves many interview questions with only small changes.

---

How to Recognise Sliding Window Problems

Ask yourself:

Does the problem mention:

• Subarray?
• Substring?
• Contiguous?

Think:

Sliding Window.

---

Does it ask:

Longest...

Shortest...

Maximum...

Minimum...

Think:

Sliding Window.

---

Can I move from one window to the next by removing one element and adding one element?

If yes,

Definitely Sliding Window.

---

Common Interview Mistakes

Mistake 1

Recalculating every window.

Example:

sum(nums[i:i+k])

inside a loop.

That becomes

O(nk)

instead of

O(n)

---

Mistake 2

Forgetting to shrink.

Many candidates only expand.

A valid variable sliding window must:

Expand

↓

Become invalid

↓

Shrink

↓

Become valid

↓

Expand again

---

Mistake 3

Using a list instead of a set/dictionary.

For

Longest substring without repeating characters

checking duplicates with a list is slow.

Use

set()

or

dict()

---

Real Interview Questions

Master these:

Easy

1. Maximum Average Subarray I ⭐⭐⭐⭐⭐

2. Maximum Sum Subarray of Size K ⭐⭐⭐⭐

---

Medium

1. Longest Substring Without Repeating Characters ⭐⭐⭐⭐⭐

2. Longest Repeating Character Replacement ⭐⭐⭐⭐⭐

3. Minimum Size Subarray Sum ⭐⭐⭐⭐

4. Permutation in String ⭐⭐⭐⭐

5. Find All Anagrams in a String ⭐⭐⭐⭐

---

Hard

1. Minimum Window Substring ⭐⭐⭐⭐⭐

---

Interview Trick

When reading a question, ask yourself these three questions:

1. Is the input contiguous? (subarray/substring)
2. Am I looking for a longest, shortest, maximum, or minimum answer?
3. Can I avoid recalculating by reusing information from the previous window?

If the answer is yes, Sliding Window is often the right approach.

---

Comparison of the First Four Topics

Pattern	Best Used For	Time Complexity
Arrays	Basic traversal and manipulation	Usually O(n)
Hash Map/Set	Fast lookups, counting, duplicates	O(n)
Two Pointers	Sorted arrays, pairs, in-place operations	O(n)
Sliding Window	Contiguous subarrays/substrings	O(n)

These four patterns alone cover a large percentage of array and string interview questions.

Next Topic

We'll move to Binary Search, where you'll learn that it's much more than searching a sorted array. Interviewers often expect you to apply it to "search on the answer" problems, making it another ⭐⭐⭐⭐⭐ pattern for coding interviews.