Framework Thinking - Neetcode 150 - Sliding Window Maximum

Here is some notes for problem Sliding Window Maximum.

1. Problem statement

Given an array nums and an integer k, return an array of the maximum values in each sliding window of size k as the window moves from left to right by one position.
Constraints usually asked about: 1 <= k <= len(nums) (but handle edge cases), nums may contain negatives and duplicates, nums length n can be large (so aim for O(n) if possible)

2. Clarifying questions

Are array values integers? (yes — but algorithm doesn’t depend on integer vs float)
Can k == 0? (usually not — assume k >= 1; if allowed, define behavior)
What to return when nums is empty or k > len(nums)? (commonly return [] or treat k = n)
Expected time/space constraints? (optimize to O(n) time, O(k) extra space)
Are duplicates allowed? (yes — must handle them)

3. Example testcases

nums = [1,3,-1,-3,5,3,6,7], k = 3 → expected [3,3,5,5,6,7]
nums = [1], k = 1 → [1]
nums = [1,1,1,1], k = 2 → [1,1,1] (duplicates)
nums = [-4,-2,-5,-1], k = 2 → [-2,-2,-1] (negatives)
nums = [], k = 3 → [] (empty)
nums = [2,1], k = 3 → [] (k > n → decide to return [])

4. Brainstorm 2,3 solutions

4.1. Brute force - O(N * K).

For each window compute max by scanning k elements.
Time: O(n*k).
Space: O(1) extra space.

4.2. Max-heap (priority queue)

Keep max-heap of current window elements (store pairs (value, index)), pop invalid indices when top is out of window

=> Same above solution, but use heap to find the max with O(logK).

Time: O(n*logk).
Space: O(k) extra space.

4.3. Monolithic Deque

Maintain a double-ended queue of indices whose corresponding values are in decreasing order (front is current window max) => Monolithic Queue.
For each new element, pop smaller elements from back, remove out-of-window indices from front.
Time: O(n).
Space: O(k).

5. Implement solutions

5.1. Brute Force - O(N * K)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []

        for i in range(len(nums) - k + 1):
            maxi = nums[i]
            for j in range(i, i + k):
                maxi = max(maxi, nums[j])
            output.append(maxi)

        return output

Time complexity: O(N * K).
Space complexity: O(1) extra space, O(n−k+1) space for the output array.

5.2. Segment Tree - O(NlogN)

Explain (Main)

Parent node covers: [start .. end]
Left child:  [start .. mid]
Right child: [mid+1 .. end]

Example

Array: [3,1,5,2,7,6] Query: [3,5] → elements [2,7,6]

Segment tree:

Parent covers [0..3] ├─ left child [0..1] └─ right child [2..3]

Leaf indexes (simplified):

0 1 2 3 4 5 3 1 5 2 7 6

l = 0 → left child [0..1]

Query starts at 2 → [0..1] partially outside query

Notes:

In case left in left subtree, or right in left subtree => It covers redundant range.
For example, you do not need to cover [start, mid] and [mid, end] => When you know left belong to [mid, end] => You can cover it in parent.
while (self.n & (self.n - 1)) != 0 => Because segment tree is balanced binary tree, so we find the power of 2 in N => For example, n = 5, init = 8 => array = 16 items.

Dry run

Index:  8  9 10 11 12 13 14 15
Leaf:   3  1  5  2  7  6  -inf -inf

            [0..7] max=7 (1)
           /             \
     [0..3] max=5 (2)   [4..7] max=7 (3)
      /       \          /       \
[0..1] 3(4) [2..3]5(5) [4..5]7(6) [6..7]-inf(7)
 / \       / \          / \       / \
3   1(8) 5  2(10)      7  6(12) -inf -inf

arr = [0, 7, 5, 7, 3, 5, 7, -inf, 3, 1, 5, 2, 7, 6, -inf, -inf]

Index:  1   2   3   4   5   6    7    8  9  10 11 12 13 14 15
Value:  7   5   7   3   5   7  -inf   3  1   5  2  7  6 -inf -inf

Index 0 is unused because the segment tree is designed to be stored in a 1-indexed array

Implement

class SegmentTree:
    def __init__(self, N, A):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.build(N, A)

    def build(self, N, A):
        self.tree = [float('-inf')] * (2 * self.n)
        for i in range(N):
            self.tree[self.n + i] = A[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = max(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, l, r):
        res = float('-inf')
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res


class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        segTree = SegmentTree(n, nums)
        output = []
        for i in range(n - k + 1):
            output.append(segTree.query(i, i + k - 1))
        return output

Time: O(NlogN).
Space: O(N)

5.3. Heap - O(NlogN) - Keep max and index in the first element, idea as monolithic queue

Idea:
- Using max heap to store [i - k + 1, i] in heap.
- Because in max heap store max value in top -store[i], but maybe the max value belonged to old index => using while heap[0][1] <= i - k to remove all the old index (prior index rather than value)
- Only pop when the largest is out of the current length => Same idea of Monolithic Queue, otherwise the largest is still in [i - k + 1, i].

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = []
        output = []
        for i in range(len(nums)):
            heapq.heappush(heap, (-nums[i], i))
            if i >= k - 1:
                while heap[0][1] <= i - k:
                    heapq.heappop(heap)
                output.append(-heap[0][0])
        return output

Worst case

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1]
k = 3

i = 0: push (−1,0) → heap size = 1
i = 1: push (−2,1) → heap size = 2
i = 2: push (−3, 2) → heap size = 2
First window complete: [1,2,3]

=> Add to heap and only pop when the largest is out of index of the heap => [10,9,8,7,6,5,4,3,2,1] => Find the last 1 and pop all the value because it out of the heap O(logN).

Time: O(NlogN).
Space: O(N).

5.4. Dynamic Programming - O(N)

Idea: Using left max and right max array.

Explain

📌 PART 1 — Fill leftMax

nums=[1,2,1,0,4,2,6]
k=3

nums    = [1 2 1 | 0 4 2 | 6]
Left Max: [1, 2, 2, 0, 4, 4, 6]

Note: leftMax[i] will store the maximum value from the start of the block to index i.

📌 PART 2 — Fill rightMax (reverse direction)

nums=[1,2,1,0,4,2,6]
k=3

nums    = [1 | 2 1 0 | 4 2 6]
Right Max: [1, 2, 2, 0, 4, 4, 6]

Note: rightMax[i] will store the maximum value from index i to the end of the block.

📌 PART 3 — Visualization

|----Block A----|----Block B----|
      ^ window starts
                    ^ window ends

| Array         | Meaning                                |
| ------------- | -------------------------------------- |
| `leftMax[i]`  | max from block beginning → i (forward) |
| `rightMax[i]` | max from i → block end (reverse)       |

Note: 👉 A window of length k always fits inside at most 2 adjacent blocks of size k, and each cover each other instead at read the index % k == 0.

Sliding windows:

nums = [1,3,-1,-3,5,3,6,7], k = 3

leftMax: [1,3,3,-3,5,5,6,7]
rightMax: [3,3,-1,5,5,6,7,7]

[1,3,-1] → max(rightMax[0], leftMax[2]) = max(3,3) = 3

[3,-1,-3] → max(rightMax[1], leftMax[3]) = max(3,-3) = 3

[...etc]

Implementation

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        leftMax = [0] * n
        rightMax = [0] * n

        leftMax[0] = nums[0]
        rightMax[n - 1] = nums[n - 1]

        for i in range(1, n):
            if i % k == 0:
                leftMax[i] = nums[i]
            else:
                leftMax[i] = max(leftMax[i - 1], nums[i])

            if (n - 1 - i) % k == 0:
                rightMax[n - 1 - i] = nums[n - 1 - i]
            else:
                rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - 1 - i])

        output = [0] * (n - k + 1)

        for i in range(n - k + 1):
            output[i] = max(leftMax[i + k - 1], rightMax[i])

        return output

Time: O(N).
Space: O(N).

5.5. Monolithic Deque - O(N)

from collections import deque
from typing import List

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

        n = len(nums)
        dq = deque()  # stores indices
        output = []

        for i in range(n):
            # Remove indices that are out of the current window
            while dq and dq[0] < i - k + 1:
                dq.popleft()

            # Remove indices whose values are less than nums[i]
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            dq.append(i)

            # Window is formed, record the maximum
            if i >= k - 1:
                output.append(nums[dq[0]])

        return output

Idea:
- Same heap but more convince => Because heap is only remove the max value that outdated, so keep more data in heap can be O(N) in heap.
- We store index in monolithic deque => And remove both outdated index and the index that value < nums[i] too.
=> More optimized storing than Heap.
Time: O(N).
Space: O(N).

6. Dry run testcases

Input:

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

Dry run each steps

| i | nums[i] | deque (indices) | window max |
| - | ------- | --------------- | ---------- |
| 0 | 1       | [0]             | -          |
| 1 | 3       | [1]             | -          |
| 2 | -1      | [1, 2]          | 3          |
| 3 | -3      | [1, 2, 3]       | 3          |
| 4 | 5       | [4]             | 5          |
| 5 | 3       | [4, 5]          | 5          |
| 6 | 6       | [6]             | 6          |
| 7 | 7       | [7]             | 7          |

November 8, 2025