Sliding Window Maximum

Description

You are given an array of integers nums and an integer k representing the size of a sliding window. The window starts at the leftmost position of the array and moves one step to the right at a time. At each position, the window covers exactly k consecutive elements.

Your task is to return an array containing the maximum value within each window position.

Think of it as looking through a rectangular frame that slides along a row of numbers — at each position you report the biggest number you can see through the frame.

Examples

Example 1

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

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

Explanation:

Window Position	Elements	Max
[1, 3, -1] -3, 5, 3, 6, 7	[1, 3, -1]	3
1, [3, -1, -3] 5, 3, 6, 7	[3, -1, -3]	3
1, 3, [-1, -3, 5] 3, 6, 7	[-1, -3, 5]	5
1, 3, -1, [-3, 5, 3] 6, 7	[-3, 5, 3]	5
1, 3, -1, -3, [5, 3, 6] 7	[5, 3, 6]	6
1, 3, -1, -3, 5, [3, 6, 7]	[3, 6, 7]	7

The window slides 6 times (n - k + 1 = 8 - 3 + 1 = 6), producing 6 maximum values.

Example 2

Input: nums = [1], k = 1

Output: [1]

Explanation: When k = 1, each element is its own window. The maximum of a single element is itself, so the output is the same as the input.

Example 3

Input: nums = [9, 8, 7, 6, 5], k = 3

Output: [9, 8, 7]

Explanation: The array is strictly decreasing. Each window's maximum is its leftmost (largest) element: [9,8,7] → 9, [8,7,6] → 8, [7,6,5] → 7. This is the worst case for brute force since the maximum is always at the start of the window.

Constraints

1 ≤ nums.length ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4
1 ≤ k ≤ nums.length

Editorial

Brute Force

Intuition

The most straightforward idea: for each window position, scan all k elements inside the window and find the maximum. Slide the window one step right and repeat.

Imagine reading a row of numbers through a cardboard cutout. At each position you point at every visible number, keep track of the biggest, write it down, then shift the cutout one position right. Simple, but you are re-reading almost every number at every position.

Step-by-Step Explanation

Let's trace through nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Step 1: First window covers indices [0, 2] → elements [1, 3, -1]. Scan: max starts at 1, then 3 > 1 so max = 3, then -1 < 3 so max stays 3. Record 3.

Step 2: Slide to window [1, 3] → elements [3, -1, -3]. Scan: max starts at 3, then -1 < 3, then -3 < 3. Max = 3. Record 3.

Step 3: Slide to window [2, 4] → elements [-1, -3, 5]. Scan: max starts at -1, then -3 < -1, then 5 > -1 so max = 5. Record 5.

Step 4: Slide to window [3, 5] → elements [-3, 5, 3]. Scan: max = 5. Record 5.

Step 5: Slide to window [4, 6] → elements [5, 3, 6]. Scan: max = 6. Record 6.

Step 6: Slide to window [5, 7] → elements [3, 6, 7]. Scan: max = 7. Record 7.

Result: [3, 3, 5, 5, 6, 7]. We performed 6 windows × 3 scans = 18 element comparisons.

Brute Force — Scan Each Window for Maximum — Watch how each sliding window is scanned element by element to find its maximum. The window slides one step right each time, and the result array grows.

Algorithm

Initialize an empty result array
For each window starting position i from 0 to n - k:
- Set max_val = nums[i]
- For each index j from i+1 to i+k-1:
  - If nums[j] > max_val, update max_val = nums[j]
- Append max_val to result
Return result

Code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;

        for (int i = 0; i <= n - k; i++) {
            int max_val = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                max_val = max(max_val, nums[j]);
            }
            result.push_back(max_val);
        }

        return result;
    }
};

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []

        for i in range(n - k + 1):
            max_val = nums[i]
            for j in range(i + 1, i + k):
                max_val = max(max_val, nums[j])
            result.append(max_val)

        return result

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];

        for (int i = 0; i <= n - k; i++) {
            int maxVal = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                maxVal = Math.max(maxVal, nums[j]);
            }
            result[i] = maxVal;
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × k)

There are (n - k + 1) window positions. For each window, we scan k elements to find the maximum. Total work: (n - k + 1) × k. In the worst case when k ≈ n/2, this approaches O(n²).

With n = 10^5 and k = 50,000, that is ~2.5 × 10^9 operations — far too slow.

Space Complexity: O(1)

Excluding the output array, only a few integer variables are used.

Why This Approach Is Not Efficient

The brute force rescans almost the entire window every time it slides by one position. When the window moves from [i, i+k-1] to [i+1, i+k], only one element leaves (nums[i]) and one element enters (nums[i+k]). Yet we throw away all our knowledge about the k-1 shared elements and rescan from scratch.

Key insight: We need a data structure that can:

Efficiently report the current maximum
Add a new element when the window extends
Remove old elements when they leave the window

A max heap (priority queue) can always report the max in O(1) and insert in O(log n). The trick is handling removals — we use "lazy deletion": leave expired elements in the heap and only remove them when they surface as the top. This reduces per-window work from O(k) to O(log n).

Better Approach - Max Heap with Lazy Deletion

Intuition

Instead of rescanning each window, keep a max heap (priority queue) that always knows the largest element. When the window slides, push the new element into the heap. Before recording the maximum, check if the heap's top element is still inside the current window. If it has expired (its index is before the window start), pop it. Repeat until the top is valid.

Think of a VIP guest list sorted by importance. When you need the most important guest in the current room, check the top of the list. If that person already left the room (expired), cross them off and check the next one. You never reorganize the entire list — you only clean up expired entries when they matter.

The heap stores pairs of (value, index) so we can check whether the top element's index is within the current window.

Step-by-Step Explanation

Let's trace with nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Step 1: Build initial heap from first k elements: insert (1,0), (3,1), (-1,2). Heap top = (3, index 1).

Step 2: Window [0,2]. Heap top index 1 is within [0,2]. Max = 3. Result: [3].

Step 3: Slide to i = 3. Insert (-3, 3) into heap. Heap top = (3, index 1). Is index 1 ≥ window_start 1? Yes, valid. Max = 3. Result: [3, 3].

Step 4: Slide to i = 4. Insert (5, 4). New heap top = (5, index 4). Is index 4 ≥ window_start 2? Yes. Max = 5. Result: [3, 3, 5].

Step 5: Slide to i = 5. Insert (3, 5). Heap top = (5, index 4). Is index 4 ≥ window_start 3? Yes. Max = 5. Result: [3, 3, 5, 5].

Step 6: Slide to i = 6. Insert (6, 6). New heap top = (6, index 6). Valid. Max = 6. Result: [3, 3, 5, 5, 6].

Step 7: Slide to i = 7. Insert (7, 7). New heap top = (7, index 7). Valid. Max = 7. Result: [3, 3, 5, 5, 6, 7].

Note: In this example, lazy deletion never triggered because the maximum always stayed within the window. With a decreasing array like [9,8,7,6,5] and k=3, the top (9,0) would need to be popped at window [1,3] since index 0 < 1.

Max Heap — Insert and Lazy Delete for Window Maximum — Watch how a max heap tracks the window maximum. New elements are inserted as the window slides. Before reading the max, expired elements at the heap top are removed.

Algorithm

Create a max heap storing (value, index) pairs
Insert the first k elements into the heap
Record the heap top as the first window's maximum
For each index i from k to n-1:
- Insert (nums[i], i) into the heap
- While the heap top's index is before the window start (i - k + 1):
  - Pop the top (lazy deletion)
- Record the heap top value as this window's maximum
Return the result array

Code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;
        // Max heap of (value, index)
        priority_queue<pair<int, int>> heap;

        for (int i = 0; i < k; i++) {
            heap.push({nums[i], i});
        }
        result.push_back(heap.top().first);

        for (int i = k; i < n; i++) {
            heap.push({nums[i], i});

            // Lazy deletion: remove expired tops
            while (heap.top().second < i - k + 1) {
                heap.pop();
            }

            result.push_back(heap.top().first);
        }

        return result;
    }
};

import heapq

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []
        # Python has min heap, so negate values for max heap
        heap = []

        for i in range(k):
            heapq.heappush(heap, (-nums[i], i))
        result.append(-heap[0][0])

        for i in range(k, n):
            heapq.heappush(heap, (-nums[i], i))

            # Lazy deletion: remove expired tops
            while heap[0][1] < i - k + 1:
                heapq.heappop(heap)

            result.append(-heap[0][0])

        return result

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // Max heap: compare by value descending, then index
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );

        for (int i = 0; i < k; i++) {
            heap.offer(new int[]{nums[i], i});
        }
        result[0] = heap.peek()[0];

        for (int i = k; i < n; i++) {
            heap.offer(new int[]{nums[i], i});

            // Lazy deletion: remove expired tops
            while (heap.peek()[1] < i - k + 1) {
                heap.poll();
            }

            result[i - k + 1] = heap.peek()[0];
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Each of the n elements is inserted into the heap exactly once — O(log n) per insert. Lazy deletions also cost O(log n) per pop. In the worst case (strictly decreasing array), all elements accumulate in the heap before being deleted, leading to O(n log n) total.

Space Complexity: O(n)

In the worst case, the heap stores all n elements (none get lazily deleted until they become the top). This happens when the array is sorted in increasing order.

Why This Approach Is Not Efficient

The max heap improves from O(n × k) to O(n log n), which is fast enough for most inputs. However, it has two drawbacks:

Space: The heap can grow to O(n) because lazy deletion leaves expired elements inside. We only clean up when they reach the top.
Time: Each insertion costs O(log n), not O(1). For n = 10^5, that is about 17 operations per element — manageable but not optimal.

Key insight: We do not actually need ALL elements in the window — only the ones that could potentially be the maximum. If element A is both larger than element B AND entered the window later (so it will stay longer), then B can never be the window maximum while A is present. We can discard B immediately.

This insight leads to a monotonic deque: a deque that maintains elements in decreasing order. The front is always the current window maximum, and insertion at the back pops any smaller elements since they are now useless. Each element enters and exits the deque at most once, giving us O(n) total time.

Optimal Approach - Monotonic Deque

Intuition

Maintain a double-ended queue (deque) that stores indices of array elements. The deque has a special property: the values at those indices are always in decreasing order from front to back. This is called a monotonic decreasing deque.

Why decreasing? The front of the deque is always the index of the largest element in the current window — that is our answer for this window. Elements behind it are smaller but entered later, so they might become the maximum after the front element leaves the window.

Two maintenance rules:

Back cleanup (maintain monotonicity): Before adding a new element, remove all indices from the back whose values are ≤ the new element. They can never be the maximum while the new element is present — it is both larger and newer.
Front cleanup (maintain window bounds): Before reading the maximum, remove the front index if it has slid out of the window.

Think of a line of candidates for "tallest person in the room." When a new, taller person enters, everyone shorter can leave — they will never be the tallest. When the room shifts (window slides), the person at the front might step out.

Step-by-Step Explanation

Let's trace with nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Step 1: i = 0, val = 1. Deque empty. Push index 0. Deque: [0]. (Values: [1])

Step 2: i = 1, val = 3. Deque back index 0 has value 1 < 3. Pop it — element 1 can never beat 3. Deque empty. Push index 1. Deque: [1]. (Values: [3])

Step 3: i = 2, val = -1. Deque back index 1 has value 3 > -1. Keep it — 3 could still be max. Push index 2. Deque: [1, 2]. (Values: [3, -1]). Window [0,2] is complete. Front = index 1, nums[1] = 3. Result: [3].

Step 4: i = 3, val = -3. Check front: index 1 ≥ window_start 1? Yes, valid. Deque back has -1 > -3. Keep. Push 3. Deque: [1, 2, 3]. (Values: [3, -1, -3]). Front max = 3. Result: [3, 3].

Step 5: i = 4, val = 5. Check front: index 1, window_start = 2. Is 1 ≥ 2? NO — expired! Pop front. Deque: [2, 3]. Now back cleanup: -3 < 5, pop 3. -1 < 5, pop 2. Deque empty. Push 4. Deque: [4]. (Values: [5]). Front max = 5. Result: [3, 3, 5].

Step 6: i = 5, val = 3. Front index 4 ≥ 3? Yes. Back value 5 > 3. Keep. Push 5. Deque: [4, 5]. (Values: [5, 3]). Front max = 5. Result: [3, 3, 5, 5].

Step 7: i = 6, val = 6. Front index 4 ≥ 4? Yes. Back cleanup: 3 < 6, pop 5. 5 < 6, pop 4. Deque empty. Push 6. Deque: [6]. Front max = 6. Result: [3, 3, 5, 5, 6].

Step 8: i = 7, val = 7. Front index 6 ≥ 5? Yes. Back: 6 < 7, pop 6. Push 7. Deque: [7]. Front max = 7. Result: [3, 3, 5, 5, 6, 7].

Monotonic Deque — Maintaining Decreasing Order for O(1) Maximum — Watch how a monotonic deque keeps only useful candidates. When a new large element arrives, smaller elements are evicted from the back. Expired elements are removed from the front. The front always holds the window maximum.

Algorithm

Create an empty deque (stores indices) and an empty result array
For each index i from 0 to n-1:
a. Front cleanup: While the deque is not empty and the front index ≤ i - k, remove from front (expired element)
b. Back cleanup: While the deque is not empty and nums[deque.back()] ≤ nums[i], remove from back (useless element — smaller and older)
c. Push index i to the back of the deque
d. If i ≥ k - 1 (window is full): append nums[deque.front()] to result
Return result

Code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;
        deque<int> dq; // stores indices

        for (int i = 0; i < n; i++) {
            // Remove expired front element
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            // Remove smaller elements from back
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            // Window is full, record the max
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []
        dq = deque()  # stores indices

        for i in range(n):
            # Remove expired front element
            if dq and dq[0] <= i - k:
                dq.popleft()

            # Remove smaller elements from back
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()

            dq.append(i)

            # Window is full, record the max
            if i >= k - 1:
                result.append(nums[dq[0]])

        return result

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // stores indices
        int idx = 0;

        for (int i = 0; i < n; i++) {
            // Remove expired front element
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }

            // Remove smaller elements from back
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }

            dq.offerLast(i);

            // Window is full, record the max
            if (i >= k - 1) {
                result[idx++] = nums[dq.peekFirst()];
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each element is pushed to the deque exactly once and popped at most once (either from the front when it expires, or from the back when a larger element arrives). Total deque operations: at most 2n. Each operation is O(1). Therefore the total time is O(n).

This is optimal — we must examine each element at least once, so O(n) is a lower bound.

Space Complexity: O(k)

The deque stores at most k indices at any time (the current window). In practice it is often much smaller because back cleanup removes elements aggressively. The result array takes O(n - k + 1) additional space but is required for the output.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Sliding Window Maximum

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Max Heap with Lazy Deletion

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Monotonic Deque

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis