Sliding Window Maximum Using Deque in DSA Java - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start

↓

Initialize empty deque

↓

For each element in array

↓

Remove indices out of window from front

↓

Remove smaller elements from back

↓

Add current index to back

↓

If window formed, record max from front

↓

Repeat until end

↓

Return max array

We slide a window over the array, keep useful elements in a deque, and record max from the front of the deque for each window.

Execution Sample

DSA Java

int[] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
Deque<Integer> dq = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
  // process deque
}

This code slides a window of size k over nums, using a deque to track max elements.

Execution Table

Step	Operation	Deque Indices	Deque Values	Window Max	Visual State
1	Add index 0	[0]	[1]	-	Deque: [1]
2	Add index 1, remove smaller from back (1 < 3)	[1]	[3]	-	Deque: [3]
3	Add index 2, no removal	[1,2]	[3,-1]	3	Window [1,3,-1], Max=3
4	Add index 3, no removal (since -3 is not greater than -1)	[1,2,3]	[3,-1,-3]	3	Window [3,-1,-3], Max=3
5	Remove index 1 (out of window), add index 4, remove smaller ( -3 < 5, -1 < 5)	[4]	[5]	5	Window [-1,-3,5], Max=5
6	Add index 5, no removal (3 < 5 is false, so no removal)	[4,5]	[5,3]	5	Window [-3,5,3], Max=5
7	Add index 6, remove smaller from back (3 < 6, 5 < 6)	[6]	[6]	6	Window [5,3,6], Max=6
8	Add index 7, remove smaller (6 < 7)	[7]	[7]	7	Window [3,6,7], Max=7
9	End of array	[7]	[7]	-	Final max array: [3,3,5,5,6,7]

💡 Reached end of array, all windows processed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
i	0	0	1	2	3	4	5	6	7	End
Deque Indices	[]	[0]	[1]	[1,2]	[1,2,3]	[4]	[4,5]	[6]	[7]	[7]
Window Max Array	[]	[]	[]	[3]	[3,3]	[3,3,5]	[3,3,5,5]	[3,3,5,5,6]	[3,3,5,5,6,7]	[3,3,5,5,6,7]

Key Moments - 3 Insights

Why do we remove indices from the front of the deque when they are out of the current window?

Because those indices represent elements no longer in the current window, so they can't be the max. See execution_table step 5 where front indices are removed.

Why do we remove smaller elements from the back before adding the current index?

Smaller elements behind the current one can't be max if current is bigger, so we remove them to keep deque max at front. See step 2 and 5 for this removal.

Why do we take the max from the front of the deque?

Because the deque is maintained in decreasing order of values, so the front always holds the max for the current window. See Window Max column in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the deque indices after processing?

A [1,4]

B [1,2,3]

C [4]

D [2,3,4]

💡 Hint

Check the Deque Indices column at step 5 in execution_table.

At which step does the window max first get recorded?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the Window Max column in execution_table to see when max appears first.

If we increase k to 4, how would the deque indices change at step 5?

A Indices out of window would be removed later, so deque might have more elements

B Deque would be empty at step 5

C Deque would only have one element at step 5

D Deque indices would be same as with k=3

💡 Hint

Increasing window size delays removal of front indices; check variable_tracker for deque changes.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of useful elements
- Remove indices out of current window from front
- Remove smaller elements from back before adding new
- Front of deque always max for current window
- Slide window, record max for each position

Full Transcript

Sliding Window Maximum Using Deque slides a window over an array and finds the maximum in each window efficiently. We keep indices in a deque, removing those out of the window from the front and smaller elements from the back. The front of the deque always holds the index of the maximum element for the current window. As we move the window, we record these maximums. This method avoids re-scanning the window each time, making it efficient.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum problem?

easy

A. To reverse the array for easier processing

B. To sort the entire array before processing windows

C. To store the actual maximum values only

D. To store indices of elements in a way that helps find the maximum in O(1) time per window

Solution

1. Step 1: Understand the role of deque

   A deque stores indices of elements in a way that the front always holds the index of the maximum element for the current window.

2. Step 2: Why use indices and not values

   Storing indices allows easy removal of elements that are out of the current window range and helps maintain order efficiently.

3. Final Answer:

   To store indices of elements in a way that helps find the maximum in O(1) time per window -> Option D

4. Quick Check:

   Deque stores indices for max tracking [OK]

Hint: Deque holds indices for max, not values, for efficient window updates [OK]

Common Mistakes:

• Storing values instead of indices
• Using deque to sort the array
• Ignoring window boundaries when removing elements

2. Which of the following Java code snippets correctly initializes a deque for sliding window maximum?

easy

A. Deque<int> dq = new ArrayDeque<>();

B. Deque<Integer> dq = new LinkedList<>();

C. Deque dq = new ArrayList<>();

D. Deque<Integer> dq = new Stack<>();

Solution

1. Step 1: Identify correct deque initialization

   In Java, Deque is an interface and LinkedList implements it. So, Deque<Integer> dq = new LinkedList<>(); is valid.

2. Step 2: Why other options are invalid

   Deque<int> dq = new ArrayDeque<>(); uses primitive int which is not allowed in generics. Deque dq = new ArrayList<>(); uses ArrayList which does not implement Deque. Deque<Integer> dq = new Stack<>(); uses Stack which is not a Deque.

3. Final Answer:

   Deque<Integer> dq = new LinkedList<>(); -> Option B

4. Quick Check:

   Use LinkedList for Deque in Java [OK]

Hint: Use LinkedList or ArrayDeque with Integer type for Deque [OK]

Common Mistakes:

• Using primitive types in generics
• Confusing ArrayList with Deque
• Using Stack instead of Deque

3. What is the output of the sliding window maximum for array [1,3,-1,-3,5,3,6,7] with window size 3?

medium

A. [3, 3, 5, 5, 6, 7]

B. [1, 3, 5, 6, 7, 7]

C. [3, -1, 5, 3, 6, 7]

D. [3, 3, 3, 5, 6, 7]

Solution

1. Step 1: Slide window and find max for each window

   Windows and 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.

2. Step 2: Collect all max values in order

   The output array is [3, 3, 5, 5, 6, 7].

3. Final Answer:

   [3, 3, 5, 5, 6, 7] -> Option A

4. Quick Check:

   Max per window = [3,3,5,5,6,7] [OK]

Hint: Check max in each window of size k sequentially [OK]

Common Mistakes:

• Confusing window boundaries
• Taking max of wrong elements
• Off-by-one errors in indexing

4. Identify the bug in this Java code snippet for sliding window maximum using deque:

Deque<Integer> dq = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
  while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
    dq.pollLast();
  }
  dq.addLast(i);
  if (dq.peekFirst() <= i - k) {
    dq.pollFirst();
  }
  if (i >= k - 1) {
    result[i - k + 1] = nums[dq.peekFirst()];
  }
}

medium

A. The deque should store values, not indices

B. The loop should start from i = 1, not 0

C. The condition to remove indices out of window should be before adding new index

D. The result array is not initialized

Solution

1. Step 1: Check order of removing out-of-window indices

   Indices out of the current window must be removed before adding the new index to maintain correct window elements.

2. Step 2: Why current order causes error

   Removing out-of-window indices after adding new index can cause incorrect max calculation because the front may be outdated.

3. Final Answer:

   The condition to remove indices out of window should be before adding new index -> Option C

4. Quick Check:

   Remove old indices before adding new [OK]

Hint: Remove old indices before adding new to deque [OK]

Common Mistakes:

• Removing out-of-window indices too late
• Storing values instead of indices
• Ignoring initialization of result array

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size 4, which of the following is the correct sliding window maximum output using a deque approach?

hard

A. [12, 12, 12, 9]

B. [4, 12, 8, 9]

C. [4, 12, 12, 9]

D. [12, 12, 8, 7]

Solution

1. Step 1: Slide window and find max for each window

   Windows and max values: [4,2,12,3] -> 12, [2,12,3,8] -> 12, [12,3,8,7] -> 12, [3,8,7,9] -> 9.

2. Step 2: Collect max values in order

   The output array is [12, 12, 12, 9].

3. Final Answer:

   [12, 12, 12, 9] -> Option A

4. Quick Check:

   Max per window = [12,12,12,9] [OK]

Hint: Check max carefully; first window max is 12, not 4 [OK]

Common Mistakes:

• Misreading first window max
• Confusing window elements
• Selecting output with wrong max values