Basic example
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3, 3, 5, 5, 6, 7]
Windows and their maximums: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7.
Full lesson preview
Find the sliding window maximum with a deque
Compute the maximum value in each sliding window of size k using a deque for O(n) time.
Python practice15 minStacks & QueuesIntermediateLast updated March 27, 2026
Problem statement
Given an array of integers nums and a window size k, return an array of the maximum values in each sliding window of length k as the window moves from left to right by one position. You must achieve O(n) time by using a deque to keep indices of useful elements. If k is larger than the array length, return an empty list. If nums is empty, return an empty list.
Task
Implement an efficient sliding window maximum algorithm using a double-ended queue (deque).
Examples
Input format
Two arguments: nums (list of integers), k (integer). Example call: sliding_window_max([1,2,3], 2)
Output format
A list of integers representing the maximum of each sliding window.
Constraints
- 0 <= len(nums) <= 10^5
- 1 <= k <= 10^5 (if k > len(nums), return [])
- Time: O(n) expected
- Space: O(k)
Samples
Sample 1
Input
nums = [4,3,2,1], k = 1
Output
[4, 3, 2, 1]
Each window of size 1 has its only element as the maximum.