239. Sliding Window Maximum

LeetCode Link: 239. Sliding Window Maximum

Problem Definition

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2:

Input: nums = [1], k = 1 Output: [1]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
1 <= k <= nums.length

Thought Process

Brute Force Approach

A straightforward way to solve the problem is to iterate over each window, calculate the maximum value for that window, and append it to the result.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        left = 0
        right = left + k
        res = []

        while right <= len(nums):
            res.append(max(nums[left:right]))
            left += 1
            right += 1

        return res

However, this method will get a Time Limit Exceeded error.

Why Brute Force Fails for Large Inputs:

Time Complexity: O(n⋅k), where n is the length of the array, and k is the window size.
For each of the n positions, you search through k elements to find the maximum.
This approach is too slow for large arrays (e.g., n=105, k=5000).

Optimized Approach: Monotonic Queue

To improve efficiency, we can use a monotonic queue to maintain the maximum element for each window in O(1) time per operation. This reduces the overall complexity to O(n).

Core Concept

A monotonic queue is a special data structure that helps us find the maximum value in a sliding window efficiently. Think of it as a "smart queue" that only keeps values that could potentially be the maximum.

Why We Need It: A Simple Example

Let's say we have array [2, 1, 4, 3] with window size 3:

When we see 4, do we need to keep track of 2 and 1?
No! Because:
- 4 is bigger than both
- 4 will be in the window longer than them
- So 2 and 1 can never be the maximum while 4 is present

Key Properties

1. Decreasing Order

Queue maintains elements in strictly decreasing order
Example:

Array:  [2, 1, 4, 3]
Queue:  [4, 3]    // 2 and 1 were discarded

2. Automatic Cleanup

Smaller elements are removed as soon as a larger element arrives
This keeps the queue minimal and efficient

Current Queue: [5, 3, 2]
New Element:   4
Final Queue:   [5, 4]    // 3 and 2 removed as they're < 4

How the Monotonic Queue Works

Push Operation (Add New Element):
When a new element is added to the window, remove all elements from the back of the queue that are smaller than the new element.
This ensures the queue maintains a decreasing order.
Pop Operation (Remove Outdated Element):
If the maximum element (front of the queue) is about to leave the sliding window, remove it from the front.
Query Maximum:
The maximum of the current window is always at the front of the queue.

Real-World Example

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

Window	Current Window Elements	Queue After Window	Maximum	Explanation
Window 1	[1, 3, -1]	[3, -1]	3	First complete window. 3 is largest
Window 2	[3, -1, -3]	[3, -1, -3]	3	Slide right. 3 still largest
Window 3	[-1, -3, 5]	[5]	5	New element 5 is largest
Window 4	[-3, 5, 3]	[5, 3]	5	5 is still largest
Window 5	[5, 3, 6]	[6]	6	New element 6 is largest
Window 6	[3, 6, 7]	[7]	7	New element 7 is largest

Solutions

Using a Custom Monotonic Queue

from collections import deque

class MonotonicQueue:
    def __init__(self):
        self.queue = deque()
    
    def pop(self, value):
        # Remove the element if it is at the front
        if self.queue and self.queue[0] == value:
            self.queue.popleft()
    
    def push(self, value):
        # Pop smaller elements from the back
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
    
    def front(self):
        # Return the largest element
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums, k):
        mq = MonotonicQueue()
        result = []
        
        # Initialize the first window
        for i in range(k):
            mq.push(nums[i])
        result.append(mq.front())
        
        # Slide the window
        for i in range(k, len(nums)):
            mq.pop(nums[i - k])   # Remove the element leaving the window
            mq.push(nums[i])      # Push the new element
            result.append(mq.front())
        
        return result

Complexity Analysis

Time Complexity: O(n).
Each element is pushed exactly once and popped at most once.
Maintaining the queue (push/pop) is amortized O(1).
Space Complexity: O(k).
The MonotonicQueue holds at most k elements (one full window).

Direct Deque Implementation

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        deque_idx = deque()  # will store indices of elements
        result = []
        
        for i in range(len(nums)):
            # Remove front if it is out of this window's range
            if deque_idx and deque_idx[0] < i - k + 1:
                deque_idx.popleft()
            
            # Remove smaller elements in the back to maintain decreasing order
            while deque_idx and nums[deque_idx[-1]] < nums[i]:
                deque_idx.pop()
            
            # Push the current element's index
            deque_idx.append(i)
            
            # Once the first window is established, record the maximum
            if i >= k - 1:
                result.append(nums[deque_idx[0]])
        
        return result