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

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

2. nums = [1], k = 1 → [1]

3. nums = [1,1,1,1], k = 2 → [1,1,1] (duplicates)

4. nums = [-4,-2,-5,-1], k = 2 → [-2,-2,-1] (negatives)

5. nums = [], k = 3 → [] (empty)

6. 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

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]
k = 5

• i = 0: push (−1,0) → heap size = 1

• i = 1: push (−2,1) → heap size = 2

• i = 2: push (−3,2) → heap size = 3

• i = 3: push (−4,3) → heap size = 4

• i = 4: push (−5,4) → heap size = 5

First window complete: [1,2,3,4,5]

• Max = 5 → output.append(5)

• Heap still contains all 5 elements

=> Add to heap and only pop when the largest is out of index of the heap

• Time: O(NlogN).

• Space: O(N).

5.4. Dynamic Programming

5.5. Monolithic Deque