Sliding Window Technique Using Deque (DSA)

Introduction

The Sliding Window Technique is one of the most important concepts in DSA interviews, especially for array and string problems. Many learners struggle with this topic because they try to solve it using brute force.

In simple words, sliding window is about looking at a small part of data at a time and moving it step by step, instead of checking everything again and again.

Real-World Meaning of Sliding Window

Think of a train window:

• You can see only a small portion of the outside at one time

• As the train moves, the view keeps changing

• You don’t look back at everything again

This is exactly how the sliding window works.

What is Sliding Window Technique?

The Sliding Window Technique is used when:

• You are given an array or string

• You need to find something in all subarrays or substrings of fixed size

Instead of recalculating from scratch, you:

• Reuse previous results

• Slide the window one step at a time

Why Brute Force is Not a Good Idea

Brute Force Approach

• Check every subarray

• Recalculate result every time

Problems

• Too slow for large input

• Time complexity becomes very high

Interviewers expect an optimized sliding window solution.

Why Deque is Used in Sliding Window Problems

Deque helps because:

• We need fast insertion and deletion from both ends

• We need to keep elements in a useful order

Deque allows us to maintain only useful elements inside the window.

Most Common Sliding Window Problem

Problem Statement

Given an array and a window size k, find the maximum element in every window of size k.

Example

Input:  [1, 3, -1, -3, 5, 3, 6, 7]
Window Size (k): 3
Output: [3, 3, 5, 5, 6, 7]

Before vs After Understanding

Without Sliding Window

• Recalculate max for every window

• Too many comparisons

With Sliding Window + Deque

• Keep only useful elements

• Move window one step

What Interviewers Are Actually Testing

Interviewers want to see:

• Can you avoid repeated work?

• Do you know how to use deque smartly?

• Can you think in terms of window movement?

Key Idea (Very Simple)

We store indexes in deque, not values.

The deque always stores indexes in such a way that:

• Front has the maximum element index

• Values are in decreasing order

Step-by-Step Logic

1. Create an empty deque

2. Loop through the array

3. Remove indexes from front if they are out of the window

4. Remove smaller elements from the back

5. Add current index to deque

6. Once window size is reached, record the front element

Dry Run Example

Array: [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Index	Value	Deque (indexes)	Output
0	1	[0]	-
1	3	[1]	-
2	-1	[1,2]	3
3	-3	[1,2,3]	3
4	5	[4]	5
5	3	[4,5]	5
6	6	[6]	6
7	7	[7]	7

One-Line Logic Before Code

Keep only useful indexes in deque so the front always gives the maximum.

Code Implementation (Concept Focused)

C++ Code

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        if (!dq.empty() && dq.front() == i - k)
            dq.pop_front();

        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

Common Beginner Mistakes

• Storing values instead of indexes

• Forgetting to remove out-of-window elements

• Confusing front and back operations

Where Sliding Window Using Deque Is Used

• Sliding Window Maximum

• Minimum in window

• Stock span problems

• Real-time analytics

Time and Space Complexity

• Time Complexity: O(n)

• Space Complexity: O(k)

Easy Summary (Explain Like I’m 10)

Imagine you are looking through a moving window and always want to know the biggest thing you see. Instead of checking everything again, you remember only the important things. Deque helps you remember them in the right order so you always know the biggest one quickly.

Summary

The Sliding Window Technique using Deque is a powerful optimization method used to solve problems involving fixed-size subarrays efficiently. By maintaining only useful elements inside a deque and sliding the window step by step, you can reduce time complexity from brute force to linear time. Mastering this technique is essential for cracking array and interview problems that require speed and smart data structure usage.