Problem of The Day: Sliding Window Maximum

6 min read 1307 words

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_heap = []
        queue = deque()
        res = []
        for i, num in enumerate(nums):
            heapq.heappush(max_heap, (-num, -i))
            queue.append((num, i))
            if len(queue) > k:
                start, j = queue.popleft()
                # max_heap.remove() is O(N), which causes Time Limit Exceeded
                max_heap.remove((-start, -j))
                heapq.heapify(max_heap)

            if len(queue) >= k:
                res.append(-max_heap[0][0])

        return res

Solution [Accepted]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Max-heap to store (-value, index). Python's heapq is a min-heap.
        max_heap = [(-nums[i], i) for i in range(k)]
        heapq.heapify(max_heap)

        res = [-max_heap[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(max_heap, (-nums[i], i))
            # Lazily remove elements that are no longer in the sliding window
            while max_heap[0][1] <= i - k:
                heapq.heappop(max_heap)

            res.append(-max_heap[0][0])

        return res

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        List<int> result = new List<int>();
        var maxHeap = new PriorityQueue<(int,int), int>();
        for (var i = 0; i < k; i++) {
            maxHeap.Enqueue((nums[i], i), -nums[i]);
        }
        result.Add(maxHeap.Peek().Item1);

        for (var i = k; i < nums.Length; i++) {
            maxHeap.Enqueue((nums[i], i), -nums[i]);
            // Lazily remove elements that are no longer in the sliding window
            while (maxHeap.Peek().Item2 <= i - k) {
                maxHeap.Dequeue();
            }
            result.Add(maxHeap.Peek().Item1);
        }
        return result.ToArray();
    }
}

• time: O(Nlogk)
• space: O(N)

Editorial

Monotonic Deque Algorithm Explanation

The algorithm uses a Monotonic Deque (Double-Ended Queue) to efficiently keep track of the maximum element in the current window in O(N) time.

1. What is a Monotonic Deque?

In this context, a “monotonic” deque is one where the elements (indices of nums) are stored such that their corresponding values in nums are always in strictly decreasing order.

• nums[dq[0]] is always the largest.
• nums[dq[1]] is the second largest (among candidates for the future), and so on.

2. Why store indices instead of values?

We store indices in the deque because we need to know if an element is still within the current sliding window. If we only stored values, we wouldn’t know when the “maximum” element has fallen out of the left side of the window.

3. Step-by-Step Logic

The algorithm works in two phases: initializing the first window and then sliding it.

A. Maintaining the Maximum (The while loop): When a new element nums[i] arrives:

• We compare it with elements already in the deque from the back.
• If nums[i] is greater than or equal to nums[dq[-1]], the older element at dq[-1] can never be the maximum again. This is because nums[i] is both larger and “younger” (it will stay in the window longer).
• We pop all such smaller elements and then add the current index i. This maintains the decreasing order.

B. Removing Outdated Elements: As the window slides (when i >= k), the element that was at the very beginning of the previous window (index i - k) is now outside the window. If that index happens to be our current maximum (dq[0]), we remove it from the front.

C. Getting the Result: Since we maintain the deque in decreasing order, the index of the maximum element for the current window is always at the front (dq[0]).

4. Complexity

• Time complexity: O(N). Each index is added to the deque exactly once and removed from the deque at most once.
• Space complexity: O(k), as the deque stores at most k indices at any time.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque() # Store indices of elements in the current window
        res = []

        # 1. Process the first 'k' elements to initialize the first window
        for i in range(k):
            # Maintain monotonic property: remove indices of elements smaller than current
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)

        # The largest element for the first window is at the front of the deque
        res.append(nums[dq[0]])

        # 2. Slide the window from index 'k' to the end of the array
        for i in range(k, len(nums)):
            # If the index at the front is outside the current window, remove it
            if dq and dq[0] == i - k:
                dq.popleft()
            
            # Maintain monotonic property: remove elements that can no longer be the maximum
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()

            dq.append(i)
            # The front of the deque always holds the index of the maximum element
            res.append(nums[dq[0]])

        return res