Abhishek Gupta

Posted on Feb 16

Sliding Window Technique — Complete Guide (DSA)

1️⃣ What is Sliding Window?

Sliding Window is an algorithmic technique used to efficiently process a contiguous subarray / substring of fixed or variable size within an array or string.

Instead of recomputing values for every subarray from scratch, we reuse previous computation while moving the window forward.

👉 Think of it as a window of size k that slides over data.

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

Window positions:
[1,3,-1]
  [3,-1,-3]
    [-1,-3,5]
      [-3,5,3]
         [5,3,6]
           [3,6,7]

2️⃣ What does “Window” mean?

A window = group of elements currently being processed together.

If k = 3, at any iteration you analyze exactly 3 elements.

So:

Window size = how many elements you analyze at once

3️⃣ How Sliding Window Works

Instead of:

For every subarray of size k:
    calculate result from scratch

We do:

Compute first window result
Then slide:
    Remove left element
    Add right element
    Update result efficiently

This reduces repeated work.

4️⃣ Example — Maximum in Subarray (Your Example)

Array:

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

Windows:

[1,3,-1]  → max = 3
[3,-1,-3] → max = 3
[-1,-3,5] → max = 5
[-3,5,3]  → max = 5
[5,3,6]   → max = 6
[3,6,7]   → max = 7

Output:

[3,3,5,5,6,7]

5️⃣ Types of Sliding Window

✅ 1. Fixed Size Window

Window size constant (k given)

Examples:

Maximum sum subarray of size k
Average of subarray size k
Max/min in window size k

✅ 2. Variable Size Window

Window expands & shrinks dynamically

Examples:

Longest substring without repeating characters
Minimum window substring
Longest subarray with sum ≤ K

6️⃣ Naive vs Sliding Window

❌ Naive Approach

For each window → scan k elements

Time:

O(n * k)

✅ Sliding Window

Reuse previous result

Time:

O(n)

Huge improvement.

7️⃣ Sliding Window Algorithm Pattern (Fixed)

1. Process first window (0 → k-1)
2. For i = k → n-1
       remove element i-k
       add element i
       update answer

8️⃣ Code — Maximum Sum Subarray Size K

JavaScript

function maxSumSubarray(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  // first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

  // slide window
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i];      // add right
    windowSum -= arr[i - k];  // remove left
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

Time: O(n)
Space: O(1)

9️⃣ Hard Version — Maximum Element in Window (Deque)

Your example problem requires monotonic deque.

Why?
Because max changes non-linearly.

Algorithm Idea

Deque stores indexes of useful elements
Maintains decreasing order.

Rules:

1. Remove out-of-window elements
2. Remove smaller elements from back
3. Add current index
4. Front = max

JavaScript Code

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {

    // remove out of window
    if (deque.length && deque[0] <= i - k) {
      deque.shift();
    }

    // remove smaller elements
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // start recording after first window
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Time: O(n)
Space: O(k)

🔟 Variable Sliding Window Pattern

Used when window size unknown.

Template

left = 0
for right in range:
    expand window

    while condition invalid:
        shrink window
        left++

    update answer

1️⃣1️⃣ Example — Longest Substring Without Repeat

function longestUnique(s) {
  const set = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {

    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }

    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

1️⃣2️⃣ Real-World Examples of Sliding Window

📊 1. Network Traffic Monitoring

Find peak bandwidth usage in last 5 minutes.

Window = last 5 min packets.

💰 2. Stock Market Analysis

Maximum price in last 30 days.

Window = 30 days.

🎥 3. Video Streaming Buffer

Analyze last N frames for compression.

🧠 4. NLP / Text Processing

Longest meaningful phrase without repetition.

📱 5. Sensor Data Processing

Average temperature last 10 readings.

🔒 6. Cybersecurity

Detect anomalies in last N requests.

1️⃣3️⃣ Time Complexity Analysis

Problem Type	Time	Space
Fixed sum/avg	O(n)	O(1)
Max/min (deque)	O(n)	O(k)
Variable window	O(n)	O(k)

Why O(n)?
Each element enters & exits window once.

1️⃣4️⃣ When to Use Sliding Window

Use when you see:

✅ Subarray
✅ Substring
✅ Contiguous segment
✅ Fixed length k
✅ Range processing
✅ Running average/sum/max
✅ Longest/shortest condition

1️⃣5️⃣ Sliding Window vs Two Pointers

Sliding window = specialized two-pointer.

Two pointers:

left, right move independently

Sliding window:

right expands
left shrinks conditionally

1️⃣6️⃣ Common Interview Problems

Must know:

Maximum sum subarray size k
Sliding window maximum
Longest substring without repeat
Minimum window substring
Longest subarray with sum ≤ K
Count subarrays with condition
Fruit into baskets
Anagrams in string

1️⃣7️⃣ Common Mistakes

❌ Forget removing left element
❌ Off-by-one window size
❌ Wrong while condition
❌ Not updating answer after shrink
❌ Using sliding window for non-contiguous problems

1️⃣8️⃣ Intuition (Most Important)

Brute force:

Recalculate everything