Sliding Window Maximum Using Deque in DSA Python - Time & Space Complexity

Time Complexity: Sliding Window Maximum Using Deque

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum in each sliding window changes as the input size grows.

Specifically, how fast can we find maximums when moving a window over an array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k + 1:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

This code finds the maximum value in every window of size k as it slides over the list nums.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop over all elements in nums.
• How many times: Each element is added and removed from the deque at most once.

How Execution Grows With Input

As the input size n grows, each element is processed a limited number of times, so the total work grows roughly in direct proportion to n.

Input Size (n)	Approx. Operations
10	About 20 operations (each element added and removed once)
100	About 200 operations
1000	About 2000 operations

Pattern observation: The operations grow linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all sliding window maximums grows directly with the size of the input list.

Common Mistake

[X] Wrong: "Because there is a nested while loop inside the for loop, the time complexity must be O(n²)."

[OK] Correct: Each element is pushed and popped from the deque only once, so the total number of operations inside the while loop across the entire run is at most n, not n times n.

Interview Connect

Understanding this efficient approach shows you can optimize problems by cleverly managing data, a skill highly valued in real-world coding challenges.

Self-Check

What if we replaced the deque with a simple list and searched for the maximum in each window? How would the time complexity change?