Sliding Window Maximum Using Deque in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the deque as an empty array.

DSA Javascript

const deque = [1];

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

A[]

B{}

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using curly braces {} which creates an object, not an array.

We use an empty array [] to represent the deque in JavaScript.

2fill in blank

medium

Complete the code to remove elements from the back of the deque while the current element is greater.

DSA Javascript

while (deque.length > 0 && nums[i] > nums[deque[[1]]]) {
  deque.pop();
}

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

A0

Bdeque[0]

C1

Ddeque.length - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 which is the first element, not the last.

We compare with the last element's index in the deque, which is at deque.length - 1.

3fill in blank

hard

Fix the error in removing elements from the front of the deque when they are out of the current window.

DSA Javascript

if (deque[0] <= i - [1]) {
  deque.shift();
}

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

A0

Bk

Cnums.length

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using i or nums.length which are not window sizes.

We remove indices from the front if they are outside the window of size k.

4fill in blank

hard

Fill both blanks to add the current index to the deque and record the maximum for the window.

DSA Javascript

deque.push([1]);
if (i >= [2] - 1) {
  result.push(nums[deque[0]]);
}

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

Ai

Bk

Ci + 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices or window sizes in the conditions.

We add the current index i to the deque. We start recording results when i reaches k - 1.

5fill in blank

hard

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

DSA Javascript

function maxSlidingWindow(nums, [1]) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length > 0 && nums[i] > nums[deque[[2]]]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[0] <= i - [3]) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

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

Ak

Bdeque.length - 1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names or indices in conditions.

The function parameter is k. We compare with the last element index deque.length - 1. We remove elements out of the window using k.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum algorithm?

easy

A. To sort the entire array before processing

B. To store all elements of the array for quick access

C. To keep track of indices of elements in the current window in decreasing order of their values

D. To reverse the array elements

Solution

1. Step 1: Understand the role of deque in the algorithm

   The deque stores indices of elements in the current window, maintaining them in decreasing order of their values to quickly find the maximum.

2. Step 2: Why other options are incorrect

   To store all elements of the array for quick access is incorrect because deque does not store all elements, only relevant indices. To sort the entire array before processing and D do not relate to the sliding window maximum logic.

3. Final Answer:

   To keep track of indices of elements in the current window in decreasing order of their values -> Option C

4. Quick Check:

   Deque stores indices in decreasing order for max [OK]

Hint: Deque keeps max candidates in order for O(1) max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Assuming deque sorts the entire array
• Confusing deque with a stack or queue without order

2. Which of the following is the correct syntax to initialize an empty deque in JavaScript for the Sliding Window Maximum algorithm?

easy

A. const deque = new ArrayDeque();

B. const deque = new Deque();

C. const deque = new Queue();

D. const deque = [];

Solution

1. Step 1: Identify JavaScript data structure for deque

   JavaScript does not have a built-in Deque class, so an empty array is used to simulate a deque.

2. Step 2: Why other options are invalid

   Options A, B, and D refer to classes not available in standard JavaScript.

3. Final Answer:

   const deque = []; -> Option D

4. Quick Check:

   Use array as deque in JS [OK]

Hint: Use array as deque in JavaScript [OK]

Common Mistakes:

• Trying to use non-existent Deque class
• Using Queue which lacks double-ended operations
• Confusing JavaScript with other languages' syntax

3. What is the output of the following code snippet?

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (deque[0] <= i - k) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

medium

A. [1, 3, -1, -3, 5, 3]

B. [3, 3, 5, 5, 6, 7]

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

D. [3, 5, 6, 7]

Solution

1. Step 1: Trace the sliding window maximum for each window

   Windows of size 3 and their max values are: [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: Confirm the result array matches the expected output

   The result array is [3, 3, 5, 5, 6, 7], matching [3, 3, 5, 5, 6, 7].

3. Final Answer:

   [3, 3, 5, 5, 6, 7] -> Option B

4. Quick Check:

   Sliding window max = [3,3,5,5,6,7] [OK]

Hint: Track max in each window using deque indices [OK]

Common Mistakes:

• Not removing indices outside the window
• Pushing values instead of indices into deque
• Incorrectly updating the result array

4. Identify the bug in the following Sliding Window Maximum code snippet:

function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[0]] <= nums[i]) {
      deque.shift();
    }
    deque.push(i);
    if (deque[0] <= i - k) {
      deque.shift();
    }
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

medium

A. The condition in the while loop should compare with the last element, not the first

B. The deque should store values, not indices

C. The if condition to remove out-of-window indices is missing

D. The result array is not being returned

Solution

1. Step 1: Analyze the while loop condition

   The while loop incorrectly compares nums[deque[0]] (front) with nums[i], but it should compare with nums[deque[deque.length - 1]] (back) to maintain decreasing order.

2. Step 2: Confirm other parts are correct

   The deque stores indices correctly, the out-of-window removal condition exists, and the result is returned properly.

3. Final Answer:

   The condition in the while loop should compare with the last element, not the first -> Option A

4. Quick Check:

   Compare with deque's last element in while loop [OK]

Hint: While loop must check deque's last element for correct order [OK]

Common Mistakes:

• Comparing with front instead of back in deque
• Storing values instead of indices in deque
• Forgetting to remove indices outside the window

5. Given an array nums = [4, 2, 12, 3, 8, 7, 9] and window size k = 4, what will be the output of the Sliding Window Maximum algorithm using a deque?

hard

A. [12, 12, 12, 9]

B. [4, 12, 8, 9]

C. [12, 3, 8, 7]

D. [4, 2, 12, 3]

Solution

1. Step 1: Identify each window and its maximum

   Windows of size 4 are: [4,2,12,3] max=12, [2,12,3,8] max=12, [12,3,8,7] max=12, [3,8,7,9] max=9.

2. Step 2: Collect the maximums in order

   The result array is [12, 12, 12, 9], matching [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 in each window by comparing edges with deque [OK]

Common Mistakes:

• Not sliding window correctly by one index
• Forgetting to remove old indices from deque
• Mixing values and indices in deque