Sliding Window Maximum Using Deque in DSA Java - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: Imagine you are analyzing temperature readings over several days. You want to find the highest temperature in every 3-day window to understand heat trends.

🎯 Goal: Build a Java program that uses a deque to find the maximum value in every sliding window of size 3 in an integer array.

📋 What You'll Learn

Create an integer array called temperatures with the exact values: {4, 3, 5, 4, 3, 3, 6, 7}

Create an integer variable called windowSize and set it to 3

Use a Deque<Integer> called deque to store indices of array elements

Implement the sliding window maximum logic using the deque

Print the maximum values for each sliding window separated by spaces

💡 Why This Matters

🌍 Real World

Sliding window maximum is used in real-time data analysis like temperature monitoring, stock price analysis, and network traffic monitoring to quickly find maximum values in moving windows.

💼 Career

Understanding sliding window techniques and using deques is important for software engineers working on performance-critical applications, data streaming, and algorithm optimization.

1

Create the temperature data array

Create an integer array called temperatures with these exact values: {4, 3, 5, 4, 3, 3, 6, 7}

DSA Java

# Create the temperatures array
# Your code here

Hint

Use int[] temperatures = {4, 3, 5, 4, 3, 3, 6, 7}; to create the array.

2

Set the sliding window size

Create an integer variable called windowSize and set it to 3

DSA Java

int[] temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
# Create windowSize variable
# Your code here

Hint

Use int windowSize = 3; to set the window size.

3

Implement sliding window maximum logic using deque

Create a Deque<Integer> called deque and write a for loop with variable i from 0 to temperatures.length. Inside the loop, remove indices from the back of deque while the current temperature is greater than or equal to the temperature at those indices. Remove indices from the front if they are out of the current window. Add the current index i to the back of deque. When i is greater than or equal to windowSize - 1, add the temperature at the front index of deque to a list called maxValues.

DSA Java

int[] temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
int windowSize = 3;
// Implement sliding window maximum logic using deque
// Your code here

Hint

Use a deque to keep indices of useful elements. Remove smaller elements from the back and remove elements out of the window from the front.

4

Print the maximum values for each sliding window

Use a for loop with variable value to iterate over maxValues and print each value followed by a space.

DSA Java

import java.util.*;

int[] temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
int windowSize = 3;
Deque deque = new ArrayDeque();
List maxValues = new ArrayList();

for (int i = 0; i = temperatures[deque.peekLast()]) {
        deque.pollLast();
    }
    if (!deque.isEmpty() && deque.peekFirst() = windowSize - 1) {
        maxValues.add(temperatures[deque.peekFirst()]);
    }
}
// Print the maxValues list
// Your code here

Hint

Use a for-each loop to print each maximum value followed by a space.

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