DSA-027 · Monotonic deque of undominated indices

Sliding Window Maximum

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21334 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the maximum of every contiguous length-k window of an integer array.

nums is non-null with 0–100,000 signed int entries. A valid width satisfies 1≤k≤nums.length. Both methods throw IllegalArgumentException for invalid k, including every k when nums is empty; null is outside the contract.
Return an int[] of length n-k+1 in window-start order. Preserve nums. Negative values and Integer.MIN_VALUE are ordinary values, so zero is not a safe maximum initializer.
Deque entries are source indices, not values. On equal heights discard the older index and retain the newer equal value, which expires later. Only maximum values are returned; no earliest-argmax tie is promised.

Examples

Input: nums=[1,3,-1,-3,5,3,6,7], k=3
Output: [3,3,5,5,6,7]
Each output belongs to the next complete length-three interval.
Input: nums=[-4,-2,-5], k=2
Output: [-2,-2]
All-negative windows still have negative maxima.

Before you start

Deque front/back operations and index-based expiration
Candidate dominance and amortized analysis

Recognize the structure

A new value dominates an older value no larger than itself: it is at least as good and will remain in future windows at least as long. A deque stores only undominated candidates, separating time-based expiration at the front from value-based removal at the back.

Try before revealing

Hint 1

Can an older smaller value ever beat a newer larger value before the newer one expires?

Hint 2

Keep undominated indices in decreasing value order.

Hint 3

Expire from the front, prune from the back, append right, then read the front.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Rescan each window

For every start, inspect k values and keep their maximum, initialized to Integer.MIN_VALUE. On [2,1,3],k=2, [2,1] yields 2 and [1,3] yields 3. This O((n-k+1)k) baseline is simple and uses O(1) other workspace; the deque avoids repeatedly considering dominated values.

Improve the baseline

Expire old indices

Before reading the answer, remove deque-front indices≤right-k. They no longer belong to the window ending at right.

Prune dominated backs

While the last candidate value≤nums[right], remove it. The newer index has at least the same value and a later expiration, so the older one can never be uniquely necessary again.

Append and emit

Append right. Candidate indices increase and values strictly decrease. Once right≥k-1, the front names the maximum of the complete window; write it at right-k+1.

Why it is correct

Ordered live candidates

After each iteration all deque indices lie in [max(0,right-k+1),right], increase from front to back, and their values strictly decrease because ties keep the newer occurrence.

Dominance preserves maxima

An expired index cannot contribute to any future window. If old index i is removed by later j with nums[j]≥nums[i], every future window that still contains i after j arrives also contains j. A chain of such domination always ends at a live candidate of at least the original value.

Correct front and amortization

Every omitted live index is dominated, so the largest live value must equal the front candidate’s value. Each index is appended once and removed at most once from either end; the nested loops therefore total O(n), not O(nk).

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayDeque;
public final class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
        int[] answer = new int[nums.length - k + 1];
        ArrayDeque<Integer> candidates = new ArrayDeque<>();
        for (int right = 0; right < nums.length; right++) {
            while (!candidates.isEmpty() && candidates.peekFirst() <= right - k) candidates.removeFirst();
            while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[right]) candidates.removeLast();
            candidates.addLast(right);
            if (right >= k - 1) answer[right - k + 1] = nums[candidates.peekFirst()];
        }
        return answer;
    }
    public static int[] baseline(int[] nums, int k) {
        if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
        int[] answer = new int[nums.length - k + 1];
        for (int start = 0; start + k <= nums.length; start++) {
            int maximum = Integer.MIN_VALUE;
            for (int i = start; i < start + k; i++) maximum = Math.max(maximum, nums[i]);
            answer[start] = maximum;
        }
        return answer;
    }
}

Read the meaningful blocks

Store indices

A bare value cannot identify when its particular occurrence expires, especially with duplicates.

Expire before output

The condition is index≤right-k, since the new left boundary is right-k+1.

Document equal-value removal

Using ≤ creates strictly decreasing candidate values and chooses the newest equal maximum. Using < would also yield correct values but retain equal candidates and change identity ties.

Complexity

O(n) time, O(k) deque workspace, and O(n-k+1) returned storage. Each source index enters once and leaves at most once; a decreasing window can retain k candidates.

The rescan baseline uses O((n-k+1)k) time, O(1) other workspace and the same output storage. A lazy-deletion heap requires careful size analysis: without eager deletion it can retain expired buried entries and grow beyond O(k).

Exact-state walkthroughs

Reveal normal and boundary traces

Expiration and dominated-candidate removal

Input: {"nums":[1,3,-1,-3,5,3,6,7],"k":3} · Result: [3,3,5,5,6,7]

Step 1 of 23: Validate width and start with no candidate indices.

No complete window exists before its kth occurrence arrives.

Original input — highlighted current interval

0: 1
1: 3
2: -1
3: -3
4: 5
5: 3
6: 6
7: 7

Deque candidates — front to back, index: value

Empty at this step.

Maximum values for completed windows

Empty at this step.

State after this step
Variable	Value
values	`[1,3,-1,-3,5,3,6,7]`
left	`0`
right	`-1`
candidateIndices	`[]`
candidateValues	`[]`
answer	`[]`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 public final class Solution {
 3     public static int[] maxSlidingWindow(int[] nums, int k) {
 4         if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
 5         int[] answer = new int[nums.length - k + 1];
 6         ArrayDeque<Integer> candidates = new ArrayDeque<>();
 7         for (int right = 0; right < nums.length; right++) {
 8             while (!candidates.isEmpty() && candidates.peekFirst() <= right - k) candidates.removeFirst();
 9             while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[right]) candidates.removeLast();
10             candidates.addLast(right);
11             if (right >= k - 1) answer[right - k + 1] = nums[candidates.peekFirst()];
12         }
13         return answer;
14     }
15     public static int[] baseline(int[] nums, int k) {
16         if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
17         int[] answer = new int[nums.length - k + 1];
18         for (int start = 0; start + k <= nums.length; start++) {
19             int maximum = Integer.MIN_VALUE;
20             for (int i = start; i < start + k; i++) maximum = Math.max(maximum, nums[i]);
21             answer[start] = maximum;
22         }
23         return answer;
24     }
25 }
26

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate width and start with no candidate indices.
No complete window exists before its kth occurrence arrives.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
-1
candidateIndices
[]
candidateValues
[]
answer
[]
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
0
candidateIndices
[0]
candidateValues
[1]
answer
[]
operation
"append"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
1
candidateIndices
[]
candidateValues
[]
answer
[]
removed
0
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
1
candidateIndices
[1]
candidateValues
[3]
answer
[]
operation
"append"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
2
candidateIndices
[1,2]
candidateValues
[3,-1]
answer
[]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
0
right
2
candidateIndices
[1,2]
candidateValues
[3,-1]
answer
[3]
operation
"emit"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
1
right
3
candidateIndices
[1,2,3]
candidateValues
[3,-1,-3]
answer
[3]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
1
right
3
candidateIndices
[1,2,3]
candidateValues
[3,-1,-3]
answer
[3,3]
operation
"emit"
Expire an index outside the current window.
An expired occurrence cannot participate now or in any future window.
values
[1,3,-1,-3,5,3,6,7]
left
2
right
4
candidateIndices
[2,3]
candidateValues
[-1,-3]
answer
[3,3]
removed
1
operation
"expire"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
2
right
4
candidateIndices
[2]
candidateValues
[-1]
answer
[3,3]
removed
3
operation
"dominate"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
2
right
4
candidateIndices
[]
candidateValues
[]
answer
[3,3]
removed
2
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
2
right
4
candidateIndices
[4]
candidateValues
[5]
answer
[3,3]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
2
right
4
candidateIndices
[4]
candidateValues
[5]
answer
[3,3,5]
operation
"emit"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
3
right
5
candidateIndices
[4,5]
candidateValues
[5,3]
answer
[3,3,5]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
3
right
5
candidateIndices
[4,5]
candidateValues
[5,3]
answer
[3,3,5,5]
operation
"emit"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
4
right
6
candidateIndices
[4]
candidateValues
[5]
answer
[3,3,5,5]
removed
5
operation
"dominate"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
4
right
6
candidateIndices
[]
candidateValues
[]
answer
[3,3,5,5]
removed
4
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
4
right
6
candidateIndices
[6]
candidateValues
[6]
answer
[3,3,5,5]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
4
right
6
candidateIndices
[6]
candidateValues
[6]
answer
[3,3,5,5,6]
operation
"emit"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[1,3,-1,-3,5,3,6,7]
left
5
right
7
candidateIndices
[]
candidateValues
[]
answer
[3,3,5,5,6]
removed
6
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[1,3,-1,-3,5,3,6,7]
left
5
right
7
candidateIndices
[7]
candidateValues
[7]
answer
[3,3,5,5,6]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[1,3,-1,-3,5,3,6,7]
left
5
right
7
candidateIndices
[7]
candidateValues
[7]
answer
[3,3,5,5,6,7]
operation
"emit"
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
[3,3,5,5,6,7]

Newest equal value replaces an older one

Input: {"nums":[5,5,1,5],"k":2} · Result: [5,5,5]

Step 1 of 12: Validate width and start with no candidate indices.

No complete window exists before its kth occurrence arrives.

Original input — highlighted current interval

0: 5
1: 5
2: 1
3: 5

Deque candidates — front to back, index: value

Empty at this step.

Maximum values for completed windows

Empty at this step.

State after this step
Variable	Value
values	`[5,5,1,5]`
left	`0`
right	`-1`
candidateIndices	`[]`
candidateValues	`[]`
answer	`[]`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 public final class Solution {
 3     public static int[] maxSlidingWindow(int[] nums, int k) {
 4         if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
 5         int[] answer = new int[nums.length - k + 1];
 6         ArrayDeque<Integer> candidates = new ArrayDeque<>();
 7         for (int right = 0; right < nums.length; right++) {
 8             while (!candidates.isEmpty() && candidates.peekFirst() <= right - k) candidates.removeFirst();
 9             while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[right]) candidates.removeLast();
10             candidates.addLast(right);
11             if (right >= k - 1) answer[right - k + 1] = nums[candidates.peekFirst()];
12         }
13         return answer;
14     }
15     public static int[] baseline(int[] nums, int k) {
16         if (k < 1 || k > nums.length) throw new IllegalArgumentException("require 1 <= k <= n");
17         int[] answer = new int[nums.length - k + 1];
18         for (int start = 0; start + k <= nums.length; start++) {
19             int maximum = Integer.MIN_VALUE;
20             for (int i = start; i < start + k; i++) maximum = Math.max(maximum, nums[i]);
21             answer[start] = maximum;
22         }
23         return answer;
24     }
25 }
26

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate width and start with no candidate indices.
No complete window exists before its kth occurrence arrives.
values
[5,5,1,5]
left
0
right
-1
candidateIndices
[]
candidateValues
[]
answer
[]
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[5,5,1,5]
left
0
right
0
candidateIndices
[0]
candidateValues
[5]
answer
[]
operation
"append"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[5,5,1,5]
left
0
right
1
candidateIndices
[]
candidateValues
[]
answer
[]
removed
0
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[5,5,1,5]
left
0
right
1
candidateIndices
[1]
candidateValues
[5]
answer
[]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[5,5,1,5]
left
0
right
1
candidateIndices
[1]
candidateValues
[5]
answer
[5]
operation
"emit"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[5,5,1,5]
left
1
right
2
candidateIndices
[1,2]
candidateValues
[5,1]
answer
[5]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[5,5,1,5]
left
1
right
2
candidateIndices
[1,2]
candidateValues
[5,1]
answer
[5,5]
operation
"emit"
Expire an index outside the current window.
An expired occurrence cannot participate now or in any future window.
values
[5,5,1,5]
left
2
right
3
candidateIndices
[2]
candidateValues
[1]
answer
[5,5]
removed
1
operation
"expire"
Discard an older candidate dominated by the entering value.
The entering occurrence is at least as large and expires later; equal values retain the newer index.
values
[5,5,1,5]
left
2
right
3
candidateIndices
[]
candidateValues
[]
answer
[5,5]
removed
2
operation
"dominate"
Append the entering index after pruning.
Live candidate indices increase, values strictly decrease, and omitted live occurrences are dominated.
values
[5,5,1,5]
left
2
right
3
candidateIndices
[3]
candidateValues
[5]
answer
[5,5]
operation
"append"
Emit the front value for the complete window.
The front dominates all other live occurrences, so it is this window’s maximum.
values
[5,5,1,5]
left
2
right
3
candidateIndices
[3]
candidateValues
[5]
answer
[5,5,5]
operation
"emit"
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
[5,5,5]

Test the contract

Input: nums=[2,-1], k=1
Output: [2,-1]
Every single value is its own maximum.
Input: nums=[2,2,1], k=3
Output: [2]
One full-array window.
Input: nums=[-2147483648], k=1
Output: [-2147483648]
Extreme negative value.
Input: nums=[], k=1
Output: IllegalArgumentException
No legal nonempty width.

Common mistakes and counterexamples

Store values without expiration identity

Counterexample: [5,5,1],k=2 contains two equal occurrences with different lifetimes.

Store indices and compare them to the left boundary.

Expire index<right-k only

Counterexample: An index equal to right-k is already outside the current window.

Remove indices≤right-k.

Initialize every maximum to zero

Counterexample: [-4,-2],k=2 has maximum -2, not zero.

Use Integer.MIN_VALUE in the baseline and actual candidates in the deque.

Follow-ups

Return window minima.

Reverse the dominance comparison to remove back values≥the entering value. Index ordering and expiration stay the same; the value invariant becomes strictly increasing.

Return the earliest maximum index.

Retain older equals by using a strict < back-removal comparison, so the oldest live equal maximum stays at the front. Update the identity tie contract and test repeated maxima explicitly.

Use timestamped streaming windows.

Store timestamps or sequence indices and expire by the actual time boundary. Count-based O(k) memory becomes a bound in terms of events retained in the time horizon; arbitrary arrival rates need a separate capacity assumption.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 99/20,000 characters

Self-review

I prove dominance using value and expiration.I state tie behavior and candidate ordering.I count deque removals amortized over the full scan.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.