Sliding Window Maximum Using Deque in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the deque for sliding window maximum.

DSA Java

Deque<Integer> deque = new [1]<>();

Drag options to blanks, or click blank then click option'

AHashSet

BArrayList

CLinkedList

DStack

Attempts:

3 left

💡 Hint

Common Mistakes

Using ArrayList instead of LinkedList for deque.

Using Stack which is LIFO, not suitable for deque operations.

We use LinkedList to create a deque in Java because it implements the Deque interface.

2fill in blank

medium

Complete the code to remove indices from the deque that are out of the current window.

DSA Java

if (!deque.isEmpty() && deque.peekFirst() [1] i - k + 1) {
    deque.pollFirst();
}

Drag options to blanks, or click blank then click option'

A<

B>

C!=

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < causes wrong indices to be removed.

Using == or != does not correctly check window boundaries.

We remove indices from the front of the deque if they are less than the start index of the current window (i - k + 1).

3fill in blank

hard

Fix the error in the code that removes smaller elements from the deque's end.

DSA Java

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

Drag options to blanks, or click blank then click option'

A>

B>=

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or >= causes incorrect elements to be removed.

Using <= removes equal elements unnecessarily.

We remove elements from the deque's end while they are smaller than the current element to maintain decreasing order.

4fill in blank

hard

Fill both blanks to correctly add the current index and record the max for the window.

DSA Java

deque.offerLast([1]);
if (i >= k - 1) result[i - k + 1] = nums[[2]];

Drag options to blanks, or click blank then click option'

Ai

Bdeque.peekFirst()

C0

Dnums[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the value instead of the index to the deque.

Using wrong index to record max in result array.

We add the current index i to the deque and record the max element at the front of the deque for the current window.

5fill in blank

hard

Fill all three blanks to complete the sliding window maximum function.

DSA Java

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0) return new int[0];
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new [1]<>();
    for (int i = 0; i < n; i++) {
        if (!deque.isEmpty() && deque.peekFirst() [2] i - k + 1) {
            deque.pollFirst();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] [3] nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

Drag options to blanks, or click blank then click option'

ALinkedList

B<

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong data structure for deque.

Using wrong comparison operators causing incorrect window max.

The function uses a LinkedList as a deque. It removes indices out of the window with < and removes smaller elements with < to maintain the max at the front.

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