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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment