← all entries
A-020● Day 202026.05.22hardleetcode #239neetcode150

Sliding Window Maximum

#array#queue#sliding-window#heap-priority-queue#monotonic-queue
↗ leetcode #239 · sliding-window-maximum
01

Problem

· problem
P.020

Sliding Window Maximum

↗ leetcode #239

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

constraints
  • · 1 ≤ nums.length ≤ 10⁵
  • · -10⁴ ≤ nums[i] ≤ 10⁴
  • · 1 ≤ k ≤ nums.length
// paraphrased summary — see source for full text
examples
example 1input → output
[1,3,-1,-3,5,3,6,7]
3
[3,3,5,5,6,7]
example 2input → output
[1]
1
[1]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Should we start outputting the maximum only when the window has exactly k elements?
  • ☐
    What data structure can efficiently maintain the maximum across multiple windows?
  • ☐
    Why must we remove elements that fall outside the current window?
  • ☐
    Why store indices instead of values in the deque?
  • ☐
    What happens if all elements in the array are identical?
  • ☐
    Could we sort the array first and then apply sliding window?
  • ☐
    Is sliding window always faster than brute force for this problem?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize output and monotonic deque
○
q = collections.deque()  # index
○
q = []  # list
○
q = collections.deque()  # value
step 2· Main loop to traverse array
○
while r < len(nums):
○
while r < len(nums) - k:
○
while r < len(nums) - 1:
step 3· Maintain monotonic property by removing smaller values│ nested
○
while q and nums[q[-1]] < nums[r]:
○
while q and nums[q[-1]] <= nums[r]:
○
while q and nums[q[-1]] > nums[r]:
○
while q and nums[q[0]] < nums[r]:
step 4· Append current index to deque│ nested
○
q.append(r)
○
q.appendleft(r)
○
q.append(nums[r])
step 5· Remove out-of-window elements from front│ nested
○
if l > q[0]:
○
if l >= q[0]:
○
if r - l >= k:
step 6· Record maximum when window is complete│ nested
○
output.append(nums[q[0]])
○
output.append(nums[q[-1]])
○
output.append(q[0])
○
output.append(max(nums[l:r+1]))
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
3
        output = []
4
        q = collections.deque()  # index
5
        l = r = 0
6
        # O(n) O(n)
7
        while r < len(nums):
8
            # pop smaller values from q
9
            while q and nums[q[-1]] < nums[r]:
10
                q.pop()
11
            q.append(r)
12
13
            # remove left val from window
14
            if l > q[0]:
15
                q.popleft()
16
17
            if (r + 1) >= k:
18
                output.append(nums[q[0]])
19
                l += 1
20
            r += 1
21
22
        return output
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,3,-1,-3,5,3,6,7]
3
→
[3,3,5,5,6,7]
case 2
[1]
1
→
[1]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.