Sliding Window Maximum Using Deque in DSA Python - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: Imagine you are analyzing the temperature readings of a city over several days. You want to find the highest temperature in every 3-day window to understand the hottest periods.

🎯 Goal: Build a program that uses a deque (double-ended queue) to find the maximum temperature in every sliding window of size 3 from a list of daily temperatures.

📋 What You'll Learn

Create a list called temperatures with the exact values: [4, 3, 5, 2, 1, 6, 7]

Create a variable called window_size and set it to 3

Use a deque from the collections module to help find the maximum in each sliding window

Print the list of maximum values for each sliding window

💡 Why This Matters

🌍 Real World

Sliding window maximum is useful in analyzing time series data like temperatures, stock prices, or sensor readings to find local peaks efficiently.

💼 Career

This technique is often asked in coding interviews and used in performance-critical applications where quick data analysis over moving windows is required.

1

Create the temperature list

Create a list called temperatures with these exact values: [4, 3, 5, 2, 1, 6, 7]

DSA Python

# Create the temperatures list with the exact values
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Set the sliding window size

Create a variable called window_size and set it to 3

DSA Python

temperatures = [4, 3, 5, 2, 1, 6, 7]
# Set the window_size variable to 3
# Your code here

Hint

Just assign the number 3 to the variable window_size.

3

Find maximums using deque

Import deque from collections. Then create an empty deque called dq and an empty list called max_values. Use a for loop with variable i over the range of the length of temperatures. Inside the loop, remove indices from the right of dq while temperatures[i] is greater than or equal to temperatures[dq[-1]]. Append i to dq. Remove indices from the left of dq if they are out of the current window (less than i - window_size + 1). If i is greater than or equal to window_size - 1, append temperatures[dq[0]] to max_values.

DSA Python

temperatures = [4, 3, 5, 2, 1, 6, 7]
window_size = 3
# Import deque and implement sliding window maximum logic
# Your code here

Hint

Use deque to store indices of useful elements. Remove smaller elements from the right. Remove elements out of the window from the left.

4

Print the maximum values

Print the list max_values to show the maximum temperature in each sliding window.

DSA Python

from collections import deque

temperatures = [4, 3, 5, 2, 1, 6, 7]
window_size = 3

dq = deque()
max_values = []

for i in range(len(temperatures)):
    while dq and temperatures[i] >= temperatures[dq[-1]]:
        dq.pop()
    dq.append(i)
    if dq[0] = window_size - 1:
        max_values.append(temperatures[dq[0]])

# Print the max_values list
# Your code here

Hint

Use print(max_values) to display the final list.