Master Sliding Window Maximum with Heap and Deque – Step-by-Step Solution

Problem Description

Given an integer array nums and a sliding window of size k that moves from the leftmost to the rightmost position one step at a time, return the maximum value inside each window.

Analysis

A naïve solution scans each window in O(k) time, resulting in O(n·k) overall complexity for an array of length n. Observing that consecutive windows share k‑1 elements enables a more efficient algorithm.

Heap (Priority Queue) Solution

Use a max‑heap (implemented in Python with a min‑heap of negated values) that stores pairs (num, index). Insert the first k elements, then for each new element insert it, repeatedly remove the heap top if its index is outside the current window, and record the heap top as the window maximum.

Storing the index allows quick validation of whether the top element belongs to the current window.

Example execution for nums = [2,3,4,2,6,2,5,1], k = 3 is illustrated step‑by‑step:

Deque (Monotonic Queue) Solution

Maintain a double‑ended queue (deque) of indices whose corresponding values are kept in strictly decreasing order. When a new element arrives, pop indices from the back while their values are smaller than the new value, then push the new index. Remove the front index if it falls outside the window. The front of the deque always holds the maximum for the current window.

The monotonic property guarantees that each index is inserted and removed at most once, yielding O(n) time.

Step‑by‑step example with the same input demonstrates the deque operations:

Python Code Implementation

import collections
class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        # double‑ended queue
        q = collections.deque()
        # initialize first window
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = [nums[q[0]]]
        # slide the window
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i - k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans

s = Solution()
print(s.maxSlidingWindow([2,3,4,2,6,2,5,1],3))