Why Sliding Window Maximum Using Deque in DSA C?

The Big Idea

Discover how a simple helper can turn a slow, repetitive task into a fast, smooth process!

The Scenario

Imagine you have a long list of daily temperatures, and you want to find the hottest day in every 3-day period. Doing this by checking each group of 3 days one by one feels like a lot of work.

The Problem

Checking every group manually means repeating many comparisons again and again. This takes a lot of time and can easily cause mistakes, especially if the list is very long.

The Solution

Using a special helper called a deque, we can keep track of the hottest days smartly. It remembers only the important days and quickly tells us the hottest day for each group without rechecking everything.

Before vs After

✗ Before

for (int i = 0; i <= n - k; i++) {
    int max = arr[i];
    for (int j = i + 1; j < i + k; j++) {
        if (arr[j] > max) max = arr[j];
    }
    printf("%d ", max);
}

✓ After

for (int i = 0; i < n; i++) {
    while (!deque_empty() && arr[deque_back()] <= arr[i])
        deque_pop_back();
    deque_push_back(i);
    if (deque_front() <= i - k)
        deque_pop_front();
    if (i >= k - 1)
        printf("%d ", arr[deque_front()]);
}

What It Enables

This method lets us find the maximum in every sliding window quickly and efficiently, even for very large lists.

Real Life Example

Think about monitoring the highest stock price every hour during a trading day to make fast decisions without checking all past prices repeatedly.

Key Takeaways

Manual checking repeats work and is slow.

Deque keeps track of important elements only.

Sliding window maximum becomes fast and easy.