Sliding Window Maximum Using Deque in DSA Java

Mental Model

Keep track of the largest values in a moving window using a special list that quickly removes smaller values.

Analogy: Imagine watching runners in a race through a window. You only care about the fastest runner visible. When a new runner enters, you ignore slower runners behind the fastest one to always know the leader.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size = 4
Deque stores indexes of elements in decreasing order of their values
Example:
Deque: [4, 5] -> points to values [6, 3]
Window: [3, 4, 6, 3]

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size = 4

Goal: Find the maximum value in every window of size 4 as it slides from left to right

Step 1: Start with first window [2,1,3,4], add indexes to deque removing smaller values

Deque: [3] -> values: [4]
Window: [2, 1, 3, 4]

Why: Keep only indexes of elements that could be maximum, remove smaller ones from back

Step 2: Slide window right by 1, remove index 0 (value 2) as it is out of window, add index 4 (value 6)

Deque: [4] -> values: [6]
Window: [1, 3, 4, 6]

Why: Remove indexes outside window and remove smaller values before adding new index

Step 3: Slide window right by 1, add index 5 (value 3), remove smaller values from back

Deque: [4, 5] -> values: [6, 3]
Window: [3, 4, 6, 3]

Why: Maintain decreasing order in deque for max at front

Step 4: Slide window right by 1, add index 6 (value 8), remove smaller values (3 and 6) from back

Deque: [6] -> values: [8]
Window: [4, 6, 3, 8]

Why: New value 8 is bigger, so remove smaller values behind it

Step 5: Slide window right by 1, add index 7 (value 9), remove smaller values (8) from back

Deque: [7] -> values: [9]
Window: [6, 3, 8, 9]

Why: Keep only potential max indexes in deque

Step 6: Slide window right by 1, add index 8 (value 10), remove smaller values (9) from back

Deque: [8] -> values: [10]
Window: [3, 8, 9, 10]

Why: Maintain max at front

Step 7: Slide window right by 1, add index 9 (value 12), remove smaller values (10) from back

Deque: [9] -> values: [12]
Window: [8, 9, 10, 12]

Why: Keep max at front

Step 8: Slide window right by 1, add index 10 (value 56), remove smaller values (12) from back

Deque: [10] -> values: [56]
Window: [9, 10, 12, 56]

Why: New max found, remove smaller values

Result:

Maximums per window: [4, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA Java

import java.util.*;

public class SlidingWindowMaximum {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Remove indexes out of current window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller values from the back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add current index
            deque.offerLast(i);

            // Record max for window starting at i-k+1
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56};
        int k = 4;
        int[] maxValues = maxSlidingWindow(nums, k);
        for (int val : maxValues) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

while (!deque.isEmpty() && deque.peekFirst() <= i - k) { deque.pollFirst(); }

Remove indexes that are out of the current window range

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); }

Remove smaller values from the back to keep deque decreasing

deque.offerLast(i);

Add current index to deque as a candidate for max

if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; }

Record the max value for the current window from front of deque

Output

4 6 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 is O(n*k) by scanning each window fully; deque approach is much faster with O(n)

Edge Cases

Empty array

Returns empty result array immediately

DSA Java

if (nums == null || k <= 0) return new int[0];

Window size equals array length

Returns single max value of entire array

DSA Java

result array size is n - k + 1, works correctly for k == n

Window size is 1

Returns original array as max of each single element window

DSA Java

Deque operations still work, no removals needed

When to Use This Pattern

When asked to find max or min in every subarray/window of fixed size efficiently, use the sliding window maximum pattern with a deque to maintain candidates.

Common Mistakes

Mistake: Not removing indexes that are out of the current window from the front of the deque
Fix: Add a check to remove front indexes if they are outside the window range

Mistake: Not removing smaller values from the back before adding new index, causing incorrect max
Fix: Remove all smaller values from the back to keep deque in decreasing order

Summary

Finds the maximum value in every sliding window of size k in an array efficiently.

Use when you need fast max queries over all windows without re-scanning each window.

Keep a deque of indexes in decreasing order of values, removing out-of-window and smaller elements.

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