Sliding Window Maximum

Problem in Plain English

Given an integer array and a window size k, slide a fixed window across the array one step at a time and return the maximum element inside each position of the window.

Problem Statement

You are given an array of integers nums, and there is a sliding window of size k which moves from the very left of the array to the very right. You can only see the k numbers in the window, and the window moves right by one position each time.

Return the maximum of each window position. For nums = [1,3,-1,-3,5,3,6,7] with k = 3 the windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7], so the answer is [3,3,5,5,6,7].

Constraints

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

Examples

Example 1

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

Each of the 6 windows contributes its maximum: 3, 3, 5, 5, 6, 7.

Example 2

Input: nums = [1], k = 1
Output: [1]

There is a single window holding the only element.

Example 3

Input: nums = [4,4,-1,-2], k = 2
Output: [4,4,-1]

Windows [4,4], [4,-1], and [-1,-2] have maxima 4, 4, and -1. The duplicate maxima occupy different indices and expire separately; the final negative-only window must not produce zero.

Intuition

A window contains k consecutive positions, and each output is the largest value in those positions. In Example 1, value 3 remains the maximum for the first two windows. Keeping only the last maximum fails when it expires: we need other candidates. A deque is a queue that permits removal at either end. Keep candidate indices ordered from oldest to newest, with values non-increasing from front to back. A newer larger value permanently makes older smaller candidates unnecessary, because the newer value expires later.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Every window stands alone, so we can scan each one directly. For each of the window starts we look at all k elements inside and keep the largest.

Step-by-Step Logic

For each start i from 0 through n-k, initialise best to nums[i], so negative-only windows work. Example 1 begins with i=0 and best=1.
Visit j=i+1 through i+k-1 and replace best only when nums[j] is larger. At i=0, j=1 changes best to 3 and j=2 leaves it at 3.
Append or store best for this window. Increase i by one and repeat, rescanning the overlap: i=1 also gives 3; i=2 gives 5.
After all n-k+1 starts, return the answers. Example 1 gives [3,3,5,5,6,7].

Why It Works

For a fixed start, best initially equals the first window value. After each inner-loop comparison it equals the largest of all window values visited so far. When the scan ends, every one of the k positions has been visited, so best is exactly that window maximum. The outer loop covers all and only legal starts in increasing order, giving one correctly ordered result per window.

Dry Run

Brute Force: variable states at each step
i / window bounds	best initial	j: value → best after comparison	result after window
0 / [0,2]	1	j=1: 3→3; j=2: -1→3	[3]
1 / [1,3]	3	j=2: -1→3; j=3: -3→3	[3,3]
2 / [2,4]	-1	j=3: -3→-1; j=4: 5→5	[3,3,5]
3 / [3,5]	-3	j=4: 5→5; j=5: 3→5	[3,3,5,5]
4 / [4,6]	5	j=5: 3→5; j=6: 6→6	[3,3,5,5,6]
5 / [5,7]	3	j=6: 6→6; j=7: 7→7	[3,3,5,5,6,7]; return

Complexity Analysis

Time Complexity

O(nk)

Space Complexity

O(1)

Let n=nums.length. Exactly n-k+1 windows are scanned, each visiting k values: O((n-k+1)k), bounded by O(nk). Only loop indices and best are auxiliary; the returned array needs O(n-k+1) space and is excluded from this auxiliary bound. Python list append and JavaScript array push are amortised O(1); Java preallocates the result.

Code

Solution.java

1class Solution {2    public int[] maxSlidingWindow(int[] nums, int k) {3        int n = nums.length;4        int[] result = new int[n - k + 1];5        for (int i = 0; i <= n - k; i++) {6            int best = nums[i];7            for (int j = i + 1; j < i + k; j++) {8                if (nums[j] > best) {9                    best = nums[j];10                }11            }12            result[i] = best;13        }14        return result;15    }16}

Hints

Hint 1

Each window overlaps the previous one in all but one element, so rescanning all k elements repeats nearly the whole job.

Hint 2

A smaller element sitting left of a larger one inside the window can never become an answer, neither now nor in any later window.

Hint 3

Keep candidate indices in a deque in non-increasing value order: the front always holds the current maximum, and entries leaving the window drop off the front.

Edge Cases

k=1 returns every input value; k=n returns just the global maximum.
Negative-only input needs best initialised from a real element: [-5,-2,-7] with k=2 gives [-2,-2].
Decreasing input keeps k candidates, exercising front expiration: [5,4,3,2,1] with k=3 gives [5,4,3].
Increasing input removes candidates from the back immediately: [1,2,3,4] with k=2 gives [2,3,4].
Equal maxima have different expiration indices. Keeping equals, as the code does, makes [4,4,-1,-2] with k=2 give [4,4,-1].

Common Mistakes and Interview Tips

Storing only values loses expiration positions; store indices and read their values from nums.
Using index<=left for expiration removes the still-active left endpoint; the condition is index<left.
Initialising a maximum to zero gives wrong results on negative-only windows.
Using JavaScript Array.shift or Python list.pop(0) moves remaining elements and can make a decreasing-input scan quadratic; use true endpoint operations.
Counting the nested while loop as O(nk) ignores that a removed index never returns; charge removals to their original append.
Interview tip: prove dominance using both the larger value and its later expiration, then state whether equal values are retained or replaced.

Key Takeaway

For fixed windows needing an extremum, discard candidates dominated by newer values and expire indices by position. A monotonic deque preserves just enough history to answer each window in one linear scan; storing indices makes value order and window membership separate checks.