Sliding Window Maximum Using Deque in DSA Java - Deep Dive

Overview - Sliding Window Maximum Using Deque

What is it?

Sliding Window Maximum Using Deque is a technique to find the largest number in every window of a fixed size as it moves through an array. A window is a small part of the array that slides from the start to the end, one step at a time. The deque (double-ended queue) helps keep track of useful elements to quickly find the maximum in each window. This method is efficient and avoids checking all elements repeatedly.

Why it matters

Without this technique, finding the maximum in every window would require checking all elements inside each window, which is slow for large arrays. This would make programs lag or use too much time, especially in real-time systems like video processing or stock price analysis. Using a deque makes the process fast and smooth, saving time and computing power.

Where it fits

Before learning this, you should understand arrays, basic loops, and queues. After this, you can explore other sliding window problems like minimums, sums, or more complex data structures like segment trees or heaps for range queries.

Mental Model

Core Idea

Keep only the candidates for maximum in a special queue that updates as the window slides, so the front always holds the current window's maximum.

Think of it like...

Imagine a line of people waiting to enter a room, but only the tallest people stay in line because shorter ones behind them can't be the tallest inside. As the line moves forward, people leave and new ones join, always keeping the tallest at the front.

Array:  [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size: 4

Deque stores indexes of elements:

Initial: []
Slide 1: [0] (2)
Slide 2: [0,1] (2,1)
Slide 3: [2] (3) - 1 removed because 3 > 1 and 2
Slide 4: [3] (4) - 3 removed because 4 > 3
Slide 5: [4] (6) - 4 removed because 6 > 4
Slide 6: [4,5] (6,3)
Slide 7: [6] (8) - 3 and 6 removed because 8 > 6
Slide 8: [7] (9) - 8 removed because 9 > 8
Slide 9: [8] (10) - 9 removed because 10 > 9
Slide 10: [9] (12) - 10 removed because 12 > 10
Slide 11: [10] (56) - 12 removed because 56 > 12

At each slide, front of deque is max of window.

Build-Up - 7 Steps

1

Foundation

Understanding Sliding Window Concept

Concept: Learn what a sliding window is and how it moves over an array.

A sliding window is a fixed-size section of an array that moves one step at a time from the start to the end. For example, if the array is [1, 3, 5, 7, 9] and the window size is 3, the windows are: - [1, 3, 5] - [3, 5, 7] - [5, 7, 9] Each window covers consecutive elements, and the window slides forward by one element each time.

Result

You can identify all windows of size k in an array by moving from left to right.

Understanding the sliding window is key because it breaks a big problem into smaller, manageable parts that move step-by-step.

2

Foundation

Basics of Deque Data Structure

Concept: Learn what a deque is and how it allows adding/removing elements from both ends.

A deque (double-ended queue) is like a line where you can add or remove people from the front or the back. This flexibility helps keep track of elements efficiently. In Java, you can use LinkedList or ArrayDeque to implement a deque.

Result

You can add or remove elements from both ends in constant time.

Knowing deque operations is essential because it lets us maintain a list of candidates for the maximum efficiently.

3

Intermediate

Maintaining Maximum Candidates in Deque

🤔Before reading on: do you think we keep all elements in the deque or only some? Commit to your answer.

Concept: Only keep elements that could be the maximum in the current or future windows.

When a new element arrives, remove all smaller elements from the back of the deque because they can't be maximum if a bigger element is after them. Then add the new element's index to the back. The front of the deque always holds the index of the largest element in the current window.

Result

Deque always contains indexes of elements in decreasing order of their values.

Understanding this pruning step prevents unnecessary comparisons and keeps the deque size small, making the algorithm efficient.

4

Intermediate

Sliding the Window and Updating Deque

🤔Before reading on: do you think we remove elements from the front when they leave the window or keep them? Commit to your answer.

Concept: Remove elements from the front if they are out of the current window's range.

As the window moves forward, check if the element at the front of the deque is outside the window (its index is less than the window's start). If yes, remove it. Then apply the candidate maintenance step for the new element. This keeps the deque valid for the current window.

Result

Deque always represents the current window's maximum candidates.

Knowing when to remove elements from the front ensures the maximum is always from the current window, avoiding stale data.

5

Intermediate

Implementing Sliding Window Maximum in Java

Concept: Combine deque operations and sliding window logic to find maximums efficiently.

Use a deque to store indexes. For each element: - Remove indexes from back while current element is greater. - Add current index to back. - Remove front if out of window. - After first window, record the element at front as max. Example code snippet: import java.util.*; public class SlidingWindowMax { 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 deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); if (deque.peekFirst() <= i - k) { deque.pollFirst(); } if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; } } return result; } }

Result

The method returns an array of maximums for each sliding window.

Seeing the full implementation connects all concepts and shows how to write efficient, clean code for this problem.

6

Advanced

Time Complexity and Efficiency Analysis

🤔Before reading on: do you think the algorithm runs in O(n*k) or O(n)? Commit to your answer.

Concept: The algorithm runs in linear time O(n) because each element is added and removed at most once.

Although there are nested loops, each element is pushed and popped from the deque only once. This means the total operations are proportional to the array size, not the window size times array size. This efficiency is why this method is preferred over naive solutions.

Result

The algorithm runs in O(n) time, much faster than O(n*k) naive approach.

Understanding the linear time complexity explains why this method scales well for large inputs.

7

Expert

Deque Behavior in Edge Cases and Large Inputs

🤔Before reading on: do you think the deque can grow larger than the window size? Commit to your answer.

Concept: The deque never grows larger than the window size and handles duplicates and large inputs gracefully.

Because smaller elements are removed when a bigger one arrives, the deque size is limited by the window size. For duplicates, indexes are stored, so equal values are handled correctly. This behavior ensures memory use stays low and performance remains stable even with repeated or large numbers.

Result

Deque size is bounded by window size, and duplicates do not break the logic.

Knowing these internal behaviors helps prevent bugs and optimize memory usage in production.

Under the Hood

The deque stores indexes of elements in decreasing order of their values. When a new element arrives, all smaller elements at the back are removed because they cannot be maximum anymore. The front always holds the index of the maximum element for the current window. As the window slides, elements outside the window range are removed from the front. This process ensures each element is added and removed at most once, making the algorithm efficient.

Why designed this way?

This design avoids checking all elements in each window by maintaining only useful candidates. Alternatives like checking every element or using heaps are slower or more complex. The deque approach balances simplicity and speed, making it ideal for real-time or large data processing.

Sliding Window Maximum Algorithm

+-----------------------------+
| Input Array:                |
| [2, 1, 3, 4, 6, 3, 8, 9]   |
+-----------------------------+
            |
            v
+-----------------------------+
| Deque stores indexes:       |
| Maintains decreasing values  |
+-----------------------------+
            |
            v
+-----------------------------+
| For each new element:        |
| - Remove smaller from back   |
| - Add new index at back     |
| - Remove front if out window |
+-----------------------------+
            |
            v
+-----------------------------+
| Front of deque = max index   |
| Output max for current window|
+-----------------------------+

Myth Busters - 3 Common Misconceptions

Quick: Do you think the deque stores the actual values or their indexes? Commit to one.

Common Belief: The deque stores the actual values of the elements to find the maximum.

Reality: The deque stores indexes of elements, not the values themselves, to track their positions and window boundaries.

Why it matters: Storing values instead of indexes makes it impossible to know if an element is outside the current window, leading to incorrect maximums.

Quick: Do you think the deque can contain elements smaller than the current maximum? Commit yes or no.

Common Belief: The deque keeps all elements in the window, regardless of size.

Reality: The deque removes smaller elements from the back when a bigger element arrives, keeping only potential maximum candidates.

Why it matters: Keeping all elements wastes time and memory, making the algorithm slower and defeating its purpose.

Quick: Do you think the algorithm runs in O(n*k) time? Commit to yes or no.

Common Belief: Because of nested loops, the algorithm runs in O(n*k) time.

Reality: Each element is added and removed at most once, so the algorithm runs in O(n) time.

Why it matters: Misunderstanding the complexity may lead to rejecting this efficient method for large data.

Expert Zone

1

The deque's size never exceeds the window size because smaller elements are removed immediately, preventing unnecessary memory use.

2

Handling duplicates requires storing indexes, not values, to distinguish between identical numbers at different positions.

3

The algorithm can be adapted to find minimums by reversing the comparison logic, showing its flexibility.

When NOT to use

Avoid this method when the window size is very large compared to the array size or when random access to maximums is needed; in such cases, segment trees or balanced binary search trees may be better.

Production Patterns

Used in real-time data streams like stock price monitoring, network traffic analysis, and video frame processing where quick maximum calculations over sliding windows are critical.

Connections

Monotonic Stack

Similar pattern of maintaining elements in order to solve range problems efficiently.

Understanding sliding window maximum helps grasp monotonic stacks used in histogram and nearest greater element problems.

Real-time Signal Processing

Sliding window maximum is used to smooth or detect peaks in signals over time windows.

Knowing this algorithm aids in designing efficient filters and detectors in engineering fields.

Project Management - Kanban Board

Both maintain a limited set of prioritized items that update as tasks progress.

Recognizing this connection helps appreciate how data structures manage dynamic priorities in workflows.

Common Pitfalls

#1 Removing elements from the front only when a bigger element arrives, not when they leave the window.

Wrong approach:

if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
// forgot to remove front element
}
// continue without removing front

Correct approach:

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

Root cause:

Misunderstanding that elements must be removed when they exit the window, not only when replaced by bigger elements.

#2 Storing values in the deque instead of indexes.

Wrong approach:

Deque deque = new ArrayDeque<>();
// storing nums[i] instead of i
deque.offerLast(nums[i]);

Correct approach:

Deque deque = new ArrayDeque<>();
// storing index i
deque.offerLast(i);

Root cause:

Not realizing that indexes are needed to check if elements are inside the current window.

#3 Not removing smaller elements from the back before adding a new element.

Wrong approach:

deque.offerLast(i); // without removing smaller elements first

Correct approach:

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

Root cause:

Failing to maintain the deque in decreasing order, which breaks the maximum tracking.

Key Takeaways

Sliding Window Maximum Using Deque efficiently finds maximums in moving windows by storing only useful candidates.

The deque stores indexes, not values, to track element positions and window boundaries.

Removing smaller elements from the back and outdated elements from the front keeps the deque valid and small.

This algorithm runs in linear time O(n), making it suitable for large data and real-time applications.

Understanding this method opens doors to solving many range query problems with similar patterns.

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