Solutions

1. Brute Force

Intuition

For every possible window of size k, we simply look at all k elements and pick the maximum.
We slide the window one step at a time, and each time we scan all elements inside it to find the max.
This method is very easy to understand but slow, because we repeatedly re-scan many of the same elements.

Algorithm

Create an empty list output to store the maximum of each window.
For each starting index i from 0 to len(nums) - k:
- Set maxi to nums[i].
- Scan all elements from i to i + k - 1 and update maxi.
- Append maxi to output.
Return output after checking all windows.

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 & Space Complexity

Time complexity: $O(n * k)$
Space complexity:
- $O(1)$ extra space.
- $O(n - k + 1)$ space for the output array.

Where $n$ is the length of the array and $k$ is the size of the window.

2. Segment Tree

Intuition

The brute-force solution recomputes the maximum for every window by scanning all k elements each time, which is slow.
A Segment Tree helps us answer “what is the maximum in this range?” much faster after some preprocessing.

Think of the segment tree as a special structure built on top of the array where:

Each node stores the maximum of a segment (range) of the array.
The root stores the maximum of the whole array.
Its children store the maximum of left half and right half, and so on.

Once we build this tree:

We can query the maximum for any range [L, R] (our sliding window) in O(log n) time.
We just slide the window and ask the segment tree for the max in each range.

So the process is:
build once → query many times efficiently.

Algorithm

Build the Segment Tree
- Start with an array tree big enough to store a full binary tree.
- Place the original elements in the leaves (second half of tree).
- For each internal node, store the maximum of its two children.
- After this step, tree[1] (the root) holds the maximum of the entire array.
Range Maximum Query (Segment Tree query(l, r)):
- Shift l and r to point to the leaves representing those indices.
- While l <= r in the tree:
  - If l is a right child, consider tree[l] in the answer and move l to the next segment.
  - If r is a left child, consider tree[r] in the answer and move r to the previous segment.
  - Move both l and r up one level by dividing by 2.
- Return the maximum found.
Sliding Window using the Segment Tree
- For each window starting at index i (from 0 to n - k):
  - Query the segment tree for the range [i, i + k - 1].
  - Append this maximum to the output list.
Return the output list containing the maximum for each sliding window.

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 & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Heap

Intuition

We want to quickly get the maximum value inside a sliding window that moves across the array.
A max-heap is perfect for this because it always lets us access the largest element instantly.

As we slide the window:

We keep inserting new elements into the heap.
Some old elements will fall out of the left side of the window.
If the largest element in the heap is no longer inside the window, we remove it.
The top of the heap always represents the current maximum for the window.

This way, we efficiently maintain the maximum even as the window moves.

Algorithm

Use a max-heap to store pairs of (value, index) for all elements we encounter.
Expand the window by inserting each new element into the heap.
Once the window size becomes k:
- Remove elements from the heap if their index is outside the current window.
- The top of the heap now gives the maximum for the window.
Add this maximum to the result list.
Continue sliding the window until the end of the array and return all collected maximums.

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

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Dynamic Programming

Intuition

Instead of recalculating the maximum for each sliding window, we can preprocess the array so that every window’s maximum can be answered in O(1) time.

We divide the array into blocks of size k.
Within each block, we build:

a leftMax array: left-to-right maximums inside each block
a rightMax array: right-to-left maximums inside each block

For any sliding window:

its left part falls inside some block, so the maximum for that region is in rightMax[i]
its right part falls inside a block, so the maximum is in leftMax[i + k - 1]

The true window maximum is the larger of those two.
This lets us compute each window's maximum instantly.

Algorithm

Split the array conceptually into blocks of size k.
Build a leftMax array:
- Scan left to right.
- For each block, restart the maximum at the block boundary.
Build a rightMax array:
- Scan right to left.
- For each block, restart the maximum at the block boundary.
For each sliding window of size k:
- The maximum is max(rightMax[window_start], leftMax[window_end]).
Return all computed maximums.

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 & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Deque

Intuition

A deque helps us efficiently track the maximum inside the sliding window.
The key idea is to keep the deque storing indices of elements in decreasing order of their values.
This guarantees that:

The front of the deque always holds the index of the current window’s maximum.
Smaller elements behind a bigger one are useless (they can never become the max later),
so we remove them when pushing a new number.
If the element at the front falls out of the window, we remove it.

By maintaining this structure, each element is added and removed at most once, giving an optimal solution.

Algorithm

Use a deque to store indices of elements in decreasing order of their values.
Expand the window by moving the right pointer:
- Before inserting the new index, remove indices whose values are smaller than the new value (they cannot be future maximums).
- Add the new index to the deque.
If the left pointer passes the front index, remove it (it’s outside the window).
Once the window reaches size k, the front of the deque represents the maximum — add it to the output.
Slide the window and repeat.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        q = deque()  # index
        l = r = 0

        while r < len(nums):
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            if l > q[0]:
                q.popleft()

            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1

        return output

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$