We keep track of the biggest numbers in the current window using a special list that quickly removes smaller numbers.
Analogy: Imagine a line of people waiting to enter a room. Only the tallest people stay in line because shorter ones behind them can't be the tallest in the room. When someone leaves the room, we check if they were the tallest and update the line accordingly.
Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size k=4
Deque stores indexes of elements in decreasing order of their values
Initial:
Deque: []
Window: []
Deque: [10] (values: [56])
Max so far: [4, 6, 8, 9, 10, 12]
Why: 56 is biggest, remove smaller values behind it
Step 13: Record max for last window at index 10 (value 56)
Max so far: [4, 6, 8, 9, 10, 12, 56]
Why: Front of deque is max for current window
Result:
Max values for each window: 4 -> 6 -> 8 -> 9 -> 10 -> 12 -> 56
Annotated Code
DSA Typescript
class Deque {
items: number[] = [];
pushBack(value: number) {
this.items.push(value);
}
popBack() {
return this.items.pop();
}
popFront() {
return this.items.shift();
}
front() {
return this.items[0];
}
back() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
function slidingWindowMaximum(nums: number[], k: number): number[] {
const deque = new Deque();
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
// Remove indexes out of current window
while (!deque.isEmpty() && deque.front()! <= i - k) {
deque.popFront(); // remove old index
}
// Remove smaller values from back
while (!deque.isEmpty() && nums[deque.back()!] < nums[i]) {
deque.popBack(); // remove smaller values
}
deque.pushBack(i); // add current index
// Start adding max to result when first window is complete
if (i >= k - 1) {
result.push(nums[deque.front()!]); // front ismax
}
}
return result;
}
// Driver code
const arr = [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56];
const k = 4;
const maxValues = slidingWindowMaximum(arr, k);
console.log(maxValues.join(' -> '));
while (!deque.isEmpty() && deque.front()! <= i - k) { deque.popFront(); }
Remove indexes that are out of the current window
while (!deque.isEmpty() && nums[deque.back()!] < nums[i]) { deque.popBack(); }
Remove smaller values from the back to keep deque decreasing
deque.pushBack(i);
Add current index to deque
if (i >= k - 1) { result.push(nums[deque.front()!]); }
Add max value for current window to result
OutputSuccess
4 -> 6 -> 8 -> 9 -> 10 -> 12 -> 56
Complexity Analysis
Time: O(n) because each element is added and removed from the deque at most once
Space: O(k) because the deque stores indexes only for the current window size
vs Alternative: Naive approach checks all k elements for each window, O(n*k), which is slower than this O(n) method
Edge Cases
Empty array
Returns empty result array without error
DSA Typescript
for (let i = 0; i < nums.length; i++) { ... }
Window size k equals 1
Each element is max of its own window, returns original array
DSA Typescript
if (i >= k - 1) { result.push(nums[deque.front()!]); }
Window size k equals array length
Returns single max value of entire array
DSA Typescript
while (!deque.isEmpty() && deque.front()! <= i - k) { deque.popFront(); }
When to Use This Pattern
When asked to find max or min in every sliding window efficiently, use a deque to keep track of candidates in decreasing order to achieve O(n) time.
Common Mistakes
Mistake: Not removing indexes that are out of the current window from the front of the deque Fix: Add a check to pop from front when deque.front() <= i - k
Mistake: Not removing smaller values from the back before adding new index, causing incorrect max Fix: Pop from back while nums[deque.back()] < nums[i] before pushing new index
Summary
Finds the maximum value in every sliding window of size k using a deque for efficient tracking.
Use when you need fast max queries over moving windows in an array.
Keep the deque storing indexes of elements in decreasing order and remove outdated or smaller elements as the window slides.
Practice
(1/5)
1. What is the main purpose of using a deque in the Sliding Window Maximum algorithm?
easy
A. To reverse the array elements
B. To store all elements of the array for quick access
C. To sort the entire array before processing
D. To keep track of indices of elements in the current window in decreasing order of their values
Solution
Step 1: Understand the role of deque in the algorithm
The deque stores indices of elements in the current window, maintaining them in decreasing order of their values to quickly find the maximum.
Step 2: Eliminate incorrect options
Options A, B, and C do not describe the deque's role in maintaining order or tracking maximums.
Final Answer:
To keep track of indices of elements in the current window in decreasing order of their values -> Option D
Quick Check:
Deque stores indices in decreasing order = D [OK]
Hint: Deque keeps max candidates in order for O(1) max retrieval [OK]
Common Mistakes:
Thinking deque stores actual values instead of indices
Assuming deque sorts the entire array
Confusing deque with a stack or queue only
2. Which of the following TypeScript code snippets correctly initializes an empty deque using an array for the Sliding Window Maximum algorithm?
easy
A. const deque: number[] = [];
B. const deque = new Deque();
C. const deque = []; deque.push(null);
D. const deque: string[] = [];
Solution
Step 1: Identify correct deque initialization in TypeScript
Using an array of numbers is the common way to simulate a deque for indices, so const deque: number[] = []; is correct.
Step 2: Check other options for errors
A pushes null which is incorrect, B uses a non-existent Deque class by default, and D uses string array which is wrong for indices.
Final Answer:
const deque: number[] = []; -> Option A
Quick Check:
Array of numbers for deque = C [OK]
Hint: Use number array for indices, no built-in Deque in TypeScript [OK]
Common Mistakes:
Using string array instead of number array
Trying to use a Deque class without importing
Pushing null or undefined initially
3. What is the output of the following TypeScript code snippet for sliding window maximum with window size 3?
function maxSlidingWindow(nums: number[], k: number): number[] {
const deque: number[] = [];
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
if (deque[0] === i - k) {
deque.shift();
}
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
medium
A. [1, 3, -1, -3, 5, 3]
B. [3, 3, 5, 5, 6, 7]
C. [3, -1, -3, 5, 3, 6]
D. [7, 6, 5, 3, -3, -1]
Solution
Step 1: Trace the sliding window maximum for each window
Windows and their max values:
[1,3,-1] -> 3
[3,-1,-3] -> 3
[-1,-3,5] -> 5
[-3,5,3] -> 5
[5,3,6] -> 6
[3,6,7] -> 7
Step 2: Confirm the output array matches these max values
The output array is [3, 3, 5, 5, 6, 7], which matches.
Final Answer:
[3, 3, 5, 5, 6, 7] -> Option B
Quick Check:
Sliding window max = [3,3,5,5,6,7] [OK]
Hint: Check max of each window manually to verify output [OK]
Common Mistakes:
Not removing indices outside the window
Incorrectly popping from deque
Mixing values and indices in deque
4. Identify the bug in the following Sliding Window Maximum code snippet and select the correct fix:
function maxSlidingWindow(nums: number[], k: number): number[] {
const deque: number[] = [];
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
if (deque[0] <= i - k) {
deque.shift();
}
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
medium
A. Change condition to 'nums[deque[deque.length - 1]] <= nums[i]' in while loop
B. Change 'deque[0] <= i - k' to 'deque[0] < i - k' in if condition
C. Remove the if condition that shifts deque
D. Change 'deque.push(i)' to 'deque.unshift(i)'
Solution
Step 1: Analyze the while loop condition
The condition 'nums[deque[deque.length - 1]] < nums[i]' does not pop elements equal to nums[i], keeping redundant candidates. It should use '<=' for strictly decreasing order.
Step 2: Check other options
B would fail to remove exactly expired indices, C removes necessary logic, D reverses order incorrectly.
Final Answer:
Change condition to 'nums[deque[deque.length - 1]] <= nums[i]' in while loop -> Option A
Quick Check:
<= in while removes equals too [OK]
Hint: Use <= in while loop to remove equal values [OK]
Common Mistakes:
Using < instead of <= in while loop
Wrong fix changing shift condition to <
Using unshift instead of push
5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size k = 4, what is the sliding window maximum output if the algorithm is modified to return the indices of maximum elements instead of values?
medium
A. [3, 4, 5, 6]
B. [0, 2, 4, 5]
C. [2, 2, 2, 6]
D. [2, 3, 4, 6]
Solution
Step 1: Find max values and their indices for each window of size 4
Windows and max indices:
[4,2,12,3] (0-3) -> 2 (12)
[2,12,3,8] (1-4) -> 2 (12)
[12,3,8,7] (2-5) -> 2 (12)
[3,8,7,9] (3-6) -> 6 (9)
Step 2: Collect indices of max elements
The indices are [2, 2, 2, 6].
Final Answer:
[2, 2, 2, 6] -> Option C
Quick Check:
Max indices per window = [2,2,2,6] [OK]
Hint: Track max element indices per window, not just values [OK]
Common Mistakes:
Returning values instead of indices
Mixing up indices when max repeats
Not updating max index when window slides
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
