LeetCode 239: Sliding Window Maximum — Step-by-Step Visual Trace

#python #leetcode #algorithms

Hard — Sliding Window | Deque | Queue | Array

The Problem

Find the maximum element in each sliding window of size k as it moves from left to right through an array. Return an array containing the maximum value for each window position.

Approach

Use a deque to maintain indices of array elements in decreasing order of their values. For each element, remove smaller elements from the back, add current index, remove indices outside the current window from front, and collect maximums when window is full.

Time: O(n) · Space: O(k)

Code

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0:
            return []

        result = []
        window = deque()

        for i, num in enumerate(nums):
            while window and nums[window[-1]] < num:
                window.pop()

            window.append(i)

            if i - window[0] >= k:
                window.popleft()

            if i >= k - 1:
                result.append(nums[window[0]])

        return result