HardBlind75ArrayQueueSliding WindowHeap

Sliding Window Maximum

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. Return the max sliding window.

Examples

Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]

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

Constraints

  • •1 <= nums.length <= 10^5
  • •-10^4 <= nums[i] <= 10^4
  • •1 <= k <= nums.length

Approaches

For each window, scan all k elements to find the maximum.

CodeT: O(n * k) | S: O(n)
def max_sliding_window(nums, k):
    result = []
    for i in range(len(nums) - k + 1):
        result.append(max(nums[i:i+k]))
    return result

Use a max heap to track the maximum element in the current window.

CodeT: O(n log n) | S: O(n)
import heapq

def max_sliding_window(nums, k):
    result = []
    max_heap = []
    for i in range(len(nums)):
        heapq.heappush(max_heap, (-nums[i], i))
        while max_heap[0][1] <= i - k:
            heapq.heappop(max_heap)
        if i >= k - 1:
            result.append(-max_heap[0][0])
    return result

Use a deque to maintain indices of elements in decreasing order.

Diagram

nums=[1,3,-1,-3,5,3,6,7], k=3 Monotonic deque maintains decreasing order Front of deque is always the max for current window
CodeT: O(n) | S: O(k)
from collections import deque

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

Complexity Comparison

Brute Force
T: O(n * k)S: O(n)

For each window, scan all k elements to find the maximum.

Max Heap
T: O(n log n)S: O(n)

Use a max heap to track the maximum element in the current window.

Monotonic Deque
T: O(n)S: O(k)

Use a deque to maintain indices of elements in decreasing order.

Common Mistakes

Not removing elements that are out of the current window from the deque

Using a max heap instead of a monotonic deque (less efficient)

Forgetting to handle the case where the window hasn't fully formed yet

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems