Sliding Window Maximum using Heap

Find the maximum in every sliding window of size k using a heap.

heap sliding-window deque array

You are given a list of integers `nums` and an integer `k` (1 ≤ k ≤ len(nums)). For every contiguous subarray (window) of length `k`, find the maximum value. Return a list of these maximums in order.

Write a function `sliding_window_max(nums, k)` that returns a list of integers.

Requirements:
- The function must handle empty `nums` by returning an empty list (though `k` is valid, keep the check for robustness).
- If `k == 0`, return an empty list.
- The solution must be efficient: O(n log k) or better. Using a max-heap is a suggested approach (Python's `heapq` is a min-heap, so store negative values).

Do not use built-in `max` on each window (which would be O(n*k)); aim for an efficient algorithm.

Constraints

- 0 ≤ len(nums) ≤ 10^5
- 1 ≤ k ≤ len(nums) (when len(nums) > 0)
- Each element is an integer in the range [-10^9, 10^9]
- Expected time complexity: O(n log k) or O(n)
- Expected space: O(n) for the output (plus heap/deque overhead)

Example

>>> sliding_window_max([1,3,-1,-3,5,3,6,7], 3)
[3,3,5,5,6,7]
>>> sliding_window_max([1], 1)
[1]
>>> sliding_window_max([], 1)
[]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

A max-heap can be simulated by storing negative values in a min-heap.

When the window moves, remove the element that falls out of the window (lazy deletion).

Track indices in the heap to know which elements are out of the current window.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.