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

Sliding Window Maximum Using Deque

📖 Scenario: Imagine you are analyzing temperature readings taken every minute. You want to find the highest temperature in every 3-minute window to monitor sudden heat spikes.

🎯 Goal: Build a program that uses a deque to find the maximum value in every sliding window of size 3 from a list of temperature readings.

📋 What You'll Learn

Create an array called temps with exactly these values: {4, 3, 5, 4, 3, 3, 6, 7}

Create an integer variable called k and set it to 3

Implement the sliding window maximum logic using a deque data structure

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 monitoring temperatures, stock prices, or network traffic to quickly find peaks in a moving time frame.

💼 Career

Understanding sliding window techniques and deque data structures is important for software engineers working on performance-critical applications and real-time data processing.

1

Create the temperature array

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

DSA C

# Create the temps array with the given values
// Your code here

Hint

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

2

Set the window size

Create an integer variable called k and set it to 3

DSA C

int temps[] = {4, 3, 5, 4, 3, 3, 6, 7};
// Create the window size variable k
// Your code here

Hint

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

3

Implement sliding window maximum using deque

Write code to find the maximum in each sliding window of size k from the temps array using a deque. Use an integer array deque to store indices, and variables front and rear to manage it. The array length is 8. Store the maximums in an integer array max_vals of size 6. Use a for loop with variable i to iterate over temps.

DSA C

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

Hint

Use a deque to keep indices of useful elements. Remove smaller elements from the rear. Remove elements out of the window from the front. Store max values after the first window.

4

Print the sliding window maximum values

Print the values stored in the max_vals array separated by spaces. Use a for loop with variable i to iterate from 0 to 5.

DSA C

int temps[] = {4, 3, 5, 4, 3, 3, 6, 7};
int k = 3;
int n = 8;
int deque[8];
int front = 0, rear = -1;
int max_vals[6];

for (int i = 0; i = front && temps[i] >= temps[deque[rear]]) {
        rear--;
    }
    rear++;
    deque[rear] = i;

    if (deque[front] = k - 1) {
        max_vals[i - k + 1] = temps[deque[front]];
    }
}

// Print the max_vals array separated by spaces
// Your code here

Hint

Use a for loop to print each element of max_vals followed by a space. Then print a newline.

Practice

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

easy

A. To store the sum of elements in each window

B. To sort the array elements before processing

C. To reverse the array for easier traversal

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 has the index of the maximum element for the current window.

2. Step 2: Why deque helps in O(1) max retrieval

   Because the deque maintains elements in decreasing order, the maximum is always at the front, allowing quick access without scanning the window.

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 max indices for O(1) max retrieval [OK]

Hint: Deque keeps max at front for quick max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Using deque to sort elements
• Using deque to store sums

2. Which of the following is the correct way to declare a deque in C for storing integer indices?

easy

A. struct deque dq; // assuming a deque struct is defined

B. deque<int> dq;

C. int dq[];

D. deque dq = new deque();

Solution

1. Step 1: Understand C data structure declaration

   C does not have built-in deque type; we use structs or arrays to implement it.

2. Step 2: Identify correct syntax

   struct deque dq; // assuming a deque struct is defined shows a struct declaration which is the correct way in C if a deque struct is defined.

3. Final Answer:

   struct deque dq; // assuming a deque struct is defined -> Option A

4. Quick Check:

   C uses structs for custom data types [OK]

Hint: Use struct for deque in C, no built-in deque type [OK]

Common Mistakes:

• Using C++ syntax like deque<int>
• Trying to declare deque like an array without size
• Using Java or other language syntax

3. What is the output of the sliding window maximum for array [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56] with window size 4?

medium

A. [3, 4, 6, 6, 8, 9, 10, 12, 56]

B. [2, 3, 4, 6, 8, 9, 10, 12]

C. [4, 6, 6, 8, 9, 10, 12, 56]

D. [6, 6, 8, 9, 10, 12, 56]

Solution

1. Step 1: Slide window and find max for each window of size 4

   Windows and max values:
   Window 1: [2,1,3,4] max=4
   Window 2: [1,3,4,6] max=6
   Window 3: [3,4,6,3] max=6
   Window 4: [4,6,3,8] max=8
   Window 5: [6,3,8,9] max=9
   Window 6: [3,8,9,10] max=10
   Window 7: [8,9,10,12] max=12
   Window 8: [9,10,12,56] max=56

2. Step 2: Collect all max values in order

   The max values are [4, 6, 6, 8, 9, 10, 12, 56]

3. Final Answer:

   [4, 6, 6, 8, 9, 10, 12, 56] -> Option C

4. Quick Check:

   Max per window = [4,6,6,8,9,10,12,56] [OK]

Hint: Slide window, track max with deque front [OK]

Common Mistakes:

• Including partial windows smaller than size 4
• Off-by-one errors in window indexing
• Confusing max values with sums

4. Given this snippet for sliding window maximum, what is the bug?

for (int i = 0; i < n; i++) {
  while (!dq.empty() && arr[dq.back()] <= arr[i])
    dq.pop_back();
  dq.push_back(i);
  if (dq.front() <= i - k)
    dq.pop_front();
  if (i >= k - 1)
    printf("%d ", arr[dq.front()]);
}

medium

A. The condition to pop front should be < instead of <=

B. No bug, code is correct

C. The condition to pop front should be checked before pushing current index

D. The order of popping from back and pushing is wrong

Solution

1. Step 1: Analyze deque maintenance logic

   The code pops smaller elements from back before pushing current index, ensuring decreasing order.

2. Step 2: Check window boundary condition

   The code pops front if the front index is out of current window (<= i-k), which is correct.

3. Step 3: Confirm output printing

   Printing starts after first full window (i >= k-1), printing max at front index.

4. Final Answer:

   No bug, code is correct -> Option B

5. Quick Check:

   Deque logic and conditions are correct [OK]

Hint: Check deque front removal after pushing current index [OK]

Common Mistakes:

• Removing front before pushing current index
• Using wrong comparison operators in conditions
• Printing output before full window

5. How would you modify the sliding window maximum algorithm using deque to find the sliding window minimum instead?

hard

A. Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back

B. Reverse the array before applying the same algorithm

C. Use a stack instead of a deque

D. Change the window size to half

Solution

1. Step 1: Understand max vs min logic in deque

   For max, we pop from back while elements are smaller or equal. For min, we pop while elements are greater or equal.

2. Step 2: Modify comparison operator

   Change condition from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] to maintain increasing order for min.

3. Final Answer:

   Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back -> Option A

4. Quick Check:

   Reverse comparison for min sliding window [OK]

Hint: Flip comparison sign to find min instead of max [OK]

Common Mistakes:

• Reversing array instead of changing comparison
• Using stack which doesn't maintain order
• Changing window size unnecessarily