Sliding Window Maximum

Problem

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^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Solution

Approach: Monotonic Decreasing Deque

The key insight is to maintain a deque that stores indices of array elements in decreasing order of their values. The front of the deque always contains the index of the maximum element in the current window.

We maintain:

deque: stores indices of elements in decreasing order of values
For each element, we:
1. Remove indices outside the current window
2. Remove indices of smaller elements (they can never be the maximum)
3. Add the current index
4. The front of the deque is the maximum for this window

Implementation

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        dq = deque()  # Stores indices

        for i in range(len(nums)):
            # Remove indices outside the window
            while dq and dq[0] < i - k + 1:
                dq.popleft()

            # Remove indices of smaller elements
            # They can never be the maximum
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            # Add current index
            dq.append(i)

            # Window is fully formed after first k elements
            if i >= k - 1:
                result.append(nums[dq[0]])

        return result

Alternative (Using Max Heap):

import heapq

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        heap = []  # Max heap: (-value, index)

        for i in range(len(nums)):
            # Add current element
            heapq.heappush(heap, (-nums[i], i))

            # Window is fully formed
            if i >= k - 1:
                # Remove elements outside window
                while heap[0][1] < i - k + 1:
                    heapq.heappop(heap)
                # Maximum is at the top
                result.append(-heap[0][0])

        return result

Complexity Analysis

Deque Approach:

Time Complexity: O(n), where n is the length of the array. Each element is added and removed from the deque at most once.
Space Complexity: O(k), for the deque which stores at most k elements.

Heap Approach:

Time Complexity: O(n log n), due to heap operations.
Space Complexity: O(n), heap can grow up to n elements in the worst case.

Key Insights

Monotonic Deque: We maintain a deque in decreasing order of values. When a new element comes in, we remove all smaller elements from the back because they can never be the maximum while the current element is in the window.
Index Storage: We store indices (not values) in the deque. This allows us to check if elements are still within the current window and access their values.
Window Formation: The first maximum appears when the window is fully formed (at index k - 1). We continue to output one maximum for each subsequent position.
Why Deque Over Heap: The deque approach is optimal at O(n) because each element enters and leaves the deque exactly once. The heap approach requires O(log n) operations per element and may accumulate stale elements.
Monotonic Property: By keeping the deque monotonically decreasing, the front always contains the maximum of the current window. Elements that are smaller and come later can never be maximal while larger earlier elements are still in the window.