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

Create an empty deque
Loop through the array
Remove indexes from front if they are out of the window
Remove smaller elements from the back
Add current index to deque
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.