Sliding Window Maximum Using Deque in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

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

DSA Java

int[] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
// Sliding window maximum output array
int[] result = slidingWindowMaximum(nums, k);
System.out.println(Arrays.toString(result));

// Assume slidingWindowMaximum is implemented correctly using deque

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

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

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

D [1, 3, -1, -3, 5, 3]

💡 Hint

Remember the sliding window moves one step at a time and the maximum is the largest number in the current window.

The sliding window maximum for each window of size 3 is calculated as follows:

• Window [1,3,-1] max is 3
• Window [3,-1,-3] max is 3
• Window [-1,-3,5] max is 5
• Window [-3,5,3] max is 5
• Window [5,3,6] max is 6
• Window [3,6,7] max is 7

So the output array is [3, 3, 5, 5, 6, 7].

🧠 Conceptual

intermediate

Understanding Deque Role in Sliding Window Maximum

Why do we use a deque (double-ended queue) to solve the sliding window maximum problem efficiently?

A Because deque stores elements in a tree structure for fast searching.

B Because deque automatically sorts elements which helps find maximum quickly.

C Because deque allows insertion and deletion from both ends in O(1) time, helping maintain candidates for max efficiently.

D Because deque duplicates elements to speed up maximum calculation.

💡 Hint

Think about how we keep track of potential maximums as the window slides.

Deque allows adding and removing elements from both ends in constant time. We use it to keep indexes of elements in decreasing order of their values. This way, the front of the deque always holds the index of the maximum element for the current window.

🔧 Debug

advanced

Identify the Error in Sliding Window Maximum Implementation

What error will this code snippet cause when running sliding window maximum? ```java Deque dq = new LinkedList<>(); int[] nums = {4, 3, 5, 4, 3, 3, 6, 7}; int k = 3; 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) { System.out.print(nums[dq.peekFirst()] + " "); } } ```

DSA Java

Deque<Integer> dq = new LinkedList<>();
int[] nums = {4, 3, 5, 4, 3, 3, 6, 7};
int k = 3;
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) {
    System.out.print(nums[dq.peekFirst()] + " ");
  }
}

A Prints incorrect maximum values because the condition to remove old indexes is wrong.

B Throws NullPointerException because dq.peekFirst() can be null when empty.

C No error; code runs correctly and prints sliding window maximum.

D Infinite loop because dq.pollLast() is called inside while without proper condition.

💡 Hint

Check the condition that removes indexes out of the current window.

The condition if (dq.peekFirst() <= i - k) should be while (dq.peekFirst() <= i - k) or at least checked carefully. Using if here can cause old indexes to remain in the deque, leading to incorrect maximum values.

📝 Syntax

advanced

Identify Syntax Error in Sliding Window Maximum Code

Which option contains a syntax error in the Java sliding window maximum implementation?

DSA Java

int[] nums = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56};
int k = 4;
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) {
    System.out.print(nums[dq.peekFirst()] + " ");
  }
}

A Replace 'if (dq.peekFirst() <= i - k)' with 'if dq.peekFirst() <= i - k' (missing parentheses).

B Replace 'while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])' with 'while !dq.isEmpty() && nums[dq.peekLast()] < nums[i]'.

C Replace 'System.out.print(nums[dq.peekFirst()] + " ");' with 'System.out.println(nums[dq.peekFirst()])'.

D Replace 'dq.addLast(i);' with 'dq.add(i);' (valid method).

💡 Hint

Check Java syntax for while loops.

In Java, the condition of a while loop must be enclosed in parentheses. Option B misses parentheses around the condition, causing a syntax error.

🚀 Application

expert

Maximum Sliding Window for Large Input Performance

You have an array of 10 million integers and need to find the maximum in every sliding window of size 1000. Which approach is best for performance and why?

A Sort each window and pick the last element as maximum, resulting in O(n*k log k) time complexity.

B Use a nested loop to check all elements in each window, resulting in O(n*k) time complexity.

C Use a hash map to store counts and find maximum by keys, resulting in O(n) but high memory usage.

D Use a deque-based sliding window maximum algorithm with O(n) time complexity.

💡 Hint

Consider time complexity and how data structures help reduce repeated work.

The deque-based algorithm processes each element once, maintaining a structure to get maximum in O(1) time per window, resulting in O(n) total time. Other methods are slower or use more memory.

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