239. Sliding Window Maximum - Explanation

Description

You are given an array of integers nums and an integer k. There is a sliding window of size k that starts at the left edge of the array. The window slides one position to the right until it reaches the right edge of the array.

Return a list that contains the maximum element in the window at each step.

Example 1:

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

Output: [2,2,4,4,6]

Explanation: 
Window position            Max
---------------           -----
[1  2  1] 0  4  2  6        2
 1 [2  1  0] 4  2  6        2
 1  2 [1  0  4] 2  6        4
 1  2  1 [0  4  2] 6        4
 1  2  1  0 [4  2  6]       6

Constraints:

1 <= nums.length <= 1000
-10,000 <= nums[i] <= 10,000
1 <= k <= nums.length

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would involve iterating through each window of size k and finding the maximum element within the window by iterating through it. This would be an O(n * k) solution. Can you think of a better way? Maybe think of a data structure that tells the current maximum element of the window in O(1) time.

Hint 2

A heap is the best data structure to use when dealing with maximum or minimum values and it takes O(1) time to get the max or min value. Here, we use a max-heap. But what should we do if the current maximum element is no longer part of the window? Can you think of a different way of adding values to the max-heap?

Hint 3

We process each window by adding elements to the heap along with their indices to track whether the maximum value is still within the current window. As we move from one window to the next, an element may go out of the window but still remain in the max-heap. Is there a way to handle this situation efficiently?

Hint 4

We can ignore those elements that are no longer part of the current window, except when the maximum value is outside the window. In that case, we remove elements from the max-heap until the maximum value belongs to the current window. Why? Because those elements will be eventually removed when the maximum element goes out of the window.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

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)$

Common Pitfalls

Storing Values Instead of Indices in the Deque

When using the deque approach, a common mistake is storing the actual values rather than their indices. Storing values makes it impossible to determine when an element has left the window, since you cannot compare positions. Always store indices in the deque and use nums[index] to access values.

Incorrect Window Boundary Checks

Many solutions fail by using wrong conditions for when to start recording results or when to shrink the window. The first valid window exists when right >= k - 1 (or equivalently right + 1 >= k). Off-by-one errors here cause either missing the first window's maximum or including results before the window is fully formed.

Not Maintaining Decreasing Order in Deque

The deque must maintain indices in decreasing order of their corresponding values. A common bug is using <= instead of < when comparing values before popping, or forgetting to pop elements altogether. This results in the front of the deque not representing the actual maximum. Always pop from the back while nums[deque.back()] < nums[current].

Forgetting to Handle the Output Array Size

The number of windows is n - k + 1, not n or n - k. Allocating an output array of the wrong size leads to index out of bounds errors or missing results. This is especially problematic when k equals the array length, where there should be exactly one result.

Incorrect Segment Tree Range Queries

When using segment trees, a frequent mistake is confusing inclusive versus exclusive range boundaries. The query range [i, i + k - 1] is inclusive on both ends for a window starting at index i. Mixing up these boundaries causes queries to include elements outside the window or miss elements at the boundaries.