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

Sliding Window Maximum Using Deque

📖 Scenario: You are analyzing temperature readings collected every hour. You want to find the highest temperature recorded in every 3-hour window to understand peak heat periods.

🎯 Goal: Build a program that uses a deque (double-ended queue) to efficiently find the maximum temperature in every sliding window of size 3.

📋 What You'll Learn

Create an array called temperatures with the exact values: [4, 3, 5, 4, 3, 3, 6, 7]

Create a variable called windowSize and set it to 3

Use a deque (array used as double-ended queue) to find the maximum in each sliding window

Print the resulting array of maximums after processing all windows

💡 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 peak values in recent data.

💼 Career

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

1

Create the temperature data array

Create an array called temperatures with these exact values: [4, 3, 5, 4, 3, 3, 6, 7]

DSA Javascript

# Create the temperatures array with the given values
# Your code here

Hint

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

2

Set the sliding window size

Create a variable called windowSize and set it to 3

DSA Javascript

const temperatures = [4, 3, 5, 4, 3, 3, 6, 7];
// Set the window size to 3
# Your code here

Hint

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

3

Implement sliding window maximum using deque

Create an empty array called deque to store indices, an empty array called maxValues to store results, and use 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. Then add i to the back of deque. Remove the front index if it is out of the current window (less than i - windowSize + 1). If i is greater than or equal to windowSize - 1, append the temperature at the front index of deque to maxValues.

DSA Javascript

const temperatures = [4, 3, 5, 4, 3, 3, 6, 7];
const windowSize = 3;
// Implement sliding window maximum using deque
# Your code here

Hint

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

4

Print the sliding window maximum results

Print the maxValues array using console.log(maxValues)

DSA Javascript

const temperatures = [4, 3, 5, 4, 3, 3, 6, 7];
const windowSize = 3;

const deque = [];
const maxValues = [];

for (let i = 0; i  0 && temperatures[i] >= temperatures[deque[deque.length - 1]]) {
        deque.pop();
    }
    deque.push(i);

    if (deque[0] = windowSize - 1) {
        maxValues.push(temperatures[deque[0]]);
    }
}
// Print the maxValues array
# Your code here

Hint

Use console.log(maxValues) to display the result.

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