Pseudo-code:

text
Initialize an empty list result
For i from 0 to length(nums) - k:
    current_max = -infinity
    For j from 0 to k - 1:
        current_max = max(current_max, nums[i + j])
    Append current_max to result
Return result

Complexity Analysis:

• Time Complexity: $O(N \cdot k)$, where $N$ is the number of elements. For every window step, we perform $k$ comparisons. In the worst case (e.g., $k = N/2$), this approaches $O(N^2)$.
• Space Complexity: $O(1)$ (excluding the output array).

Why it fails: The constraints state that nums.length can be up to $10^5$. If $k$ is large, an $O(N^2)$ approach will perform approximately $10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed by online judges. This results in a Time Limit Exceeded (TLE) error.

Core Insight for Sliding Window Maximum

The transition from the brute force approach to the optimal solution relies on a key observation about "useless" elements.

Consider two indices $i$ and $j$ such that $i < j$ (index $i$ comes before $j$) and nums[i] <= nums[j]. If both indices are currently inside the sliding window, index $i$ can never be the maximum. Why?

1. nums[j] is greater than or equal to nums[i], so nums[i] is not the max right now.
2. As the window slides, index $i$ will exit the window before index $j$. Therefore, nums[i] will never become the maximum in the future while nums[j] is present.

This implies that we can discard nums[i] immediately. We only need to store elements that have the potential to be the maximum. This logic leads us to maintain a data structure where elements are stored in strictly decreasing order.

Visual Description: Imagine the data structure as a queue of indices. As we scan the array from left to right:

1. ** entering element:** When a new element enters, it eliminates all elements at the back of the queue that are smaller than or equal to it. This maintains the decreasing invariant.
2. Exiting element: If the index at the front of the queue falls out of the current window range (i.e., index <= current_index - k), it is removed.
3. Result: The element corresponding to the index at the front of the queue is always the maximum for the current window.

Execution Flow

Let's trace the algorithm with nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3.

1. i = 0, val = 1: Deque: [0] (val: 1).
2. i = 1, val = 3: Back (1) < 3. Pop 0. Push 1. Deque: [1] (val: 3).
3. i = 2, val = -1: Back (3) > -1. Push 2. Deque: [1, 2] (vals: 3, -1). Window [0, 2] complete. Max is nums[1] = 3.
4. i = 3, val = -3: Front index 1 is valid (range 1-3). Back (-1) > -3. Push 3. Deque: [1, 2, 3] (vals: 3, -1, -3). Max is nums[1] = 3.
5. i = 4, val = 5: Front index 1 is expired (range 2-4). Pop 1. Back (-3) < 5, pop 3. Back (-1) < 5, pop 2. Push 4. Deque: [4] (val: 5). Max is nums[4] = 5.
6. i = 5, val = 3: Back (5) > 3. Push 5. Deque: [4, 5] (vals: 5, 3). Max is nums[4] = 5.
7. i = 6, val = 6: Front index 4 is valid. Back (3) < 6, pop 5. Back (5) < 6, pop 4. Push 6. Deque: [6] (val: 6). Max is nums[6] = 6.
8. i = 7, val = 7: Back (6) < 7, pop 6. Push 7. Deque: [7] (val: 7). Max is nums[7] = 7.

Result: [3, 3, 5, 5, 6, 7]

Proof of Correctness

The correctness relies on the invariant that the deque is strictly decreasing.

1. Max at Front: Since the deque is sorted in descending order of values, the front always holds the index of the largest value.
2. Validity: We explicitly remove indices that fall out of the window (i - k). Thus, the front is always a valid index within the current window.
3. Completeness: We only remove elements that are smaller than the current element being added. A removed element could never be the maximum for any future window that includes the current element, because the current element is larger and persists longer.

Reference Implementation

C++ Solution for LeetCode 239

cpp
#include <vector>
#include <deque>

class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::deque<int> dq; // Stores indices
        std::vector<int> result;
        
        for (int i = 0; i < nums.size(); ++i) {
            // 1. Remove indices that are out of the current window
            if (!dq.empty() && dq.front() == i - k) {
                dq.pop_front();
            }
            
            // 2. Remove indices whose corresponding values are less than nums[i]
            // These elements can never be the maximum
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            
            // 3. Add current index
            dq.push_back(i);
            
            // 4. Add the maximum (front of deque) to result
            // The first window ends at index k - 1
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 239

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int resultIdx = 0;
        
        // Deque stores indices
        Deque<Integer> dq = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 1. Remove indices out of the current window
            if (!dq.isEmpty() && dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            
            // 2. Remove elements smaller than current from the back
            // Maintain decreasing order
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            
            // 3. Add current index
            dq.offerLast(i);
            
            // 4. Add max to result once the first window is formed
            if (i >= k - 1) {
                result[resultIdx++] = nums[dq.peekFirst()];
            }
        }
        
        return result;
    }
}

Python Solution for LeetCode 239

python
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque() # Stores indices
        result = []
        
        for i in range(len(nums)):
            # 1. Remove index if it's out of the current window
            if dq and dq[0] == i - k:
                dq.popleft()
            
            # 2. Remove indices from back if their values are smaller than current
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
                
            # 3. Add current index
            dq.append(i)
            
            # 4. Append max to result (only after first window is complete)
            if i >= k - 1:
                result.append(nums[dq[0]])
                
        return result