Sliding Window Maximum Using Deque in DSA C - Time & Space Complexity

Time Complexity: Sliding Window Maximum Using Deque

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum in each sliding window changes as the input size grows.

How does the algorithm handle many elements efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void slidingWindowMax(int arr[], int n, int k) {
    int deque[n];
    int front = 0, back = -1;
    for (int i = 0; i < n; i++) {
        while (front <= back && arr[deque[back]] < arr[i]) back--;
        deque[++back] = i;
        if (deque[front] == i - k) front++;
        if (i >= k - 1) printf("%d ", arr[deque[front]]);
    }
}
    

This code finds the maximum value in every window of size k in the array using a deque.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop runs through all elements once.
• How many times: Each element is added and removed from the deque at most once.

How Execution Grows With Input

As the input size grows, each element is processed a limited number of times, so the total work grows roughly in direct proportion to the input size.

Input Size (n)	Approx. Operations
10	About 20 operations
100	About 200 operations
1000	About 2000 operations

Pattern observation: The operations grow linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Since there is a nested while inside the for loop, the time complexity must be O(n²)."

[OK] Correct: Each element is pushed and popped from the deque only once, so the inner loop does not run n times for each element.

Interview Connect

Understanding this efficient approach shows you can handle problems that need fast sliding window calculations, a common real-world need.

Self-Check

"What if we used a simple array instead of a deque to track maximums? How would the time complexity change?"