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.