Sliding Window Maximum Using Deque in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

A deque helps keep track of indices of elements in the current window in a way that the front always holds the index of the maximum element. It allows efficient insertion and removal from both ends to maintain the maximum in O(1) amortized time per operation.

intermediate

In the Sliding Window Maximum algorithm using deque, why do we remove elements from the back of the deque when a new element arrives?

We remove elements from the back if they are smaller than the new element because they cannot be the maximum if a bigger element is present later. This keeps the deque elements in decreasing order of their values.

beginner

What does the deque store in the Sliding Window Maximum algorithm?

The deque stores indices of elements from the array, not the elements themselves. This helps to check if an element is out of the current window and to access the element's value easily.

intermediate

How do you know when to remove the front element of the deque in the Sliding Window Maximum algorithm?

If the index at the front of the deque is outside the current window (less than current index minus window size plus one), it should be removed because it is no longer part of the window.

beginner

What is the time complexity of the Sliding Window Maximum algorithm using a deque?

The time complexity is O(n) because each element is added and removed from the deque at most once, making all operations linear in total.

What does the deque store in the Sliding Window Maximum algorithm?

A Window sizes

B Actual element values

C Sum of elements

D Indices of elements

The deque stores indices to efficiently check window boundaries and access element values.

Why do we remove elements from the back of the deque when a new element arrives?

A Because they are smaller than the new element

B Because they are larger than the new element

C To keep the deque size fixed

D To maintain ascending order

Smaller elements at the back are removed because the new bigger element will overshadow them for maximum.

When do we remove the front element of the deque?

A When it is outside the current window

B When it is the maximum element

C When it is inside the current window

D When the deque is empty

The front element is removed if its index is outside the current sliding window.

What is the time complexity of the Sliding Window Maximum algorithm using deque?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

Each element is added and removed at most once, so the total time is linear.

What is the main advantage of using a deque for this problem?

A It sorts the window elements

B It allows constant time access to the maximum

C It stores all elements permanently

D It reduces memory usage

Deque maintains elements in a way that the maximum is always at the front, allowing O(1) access.

Explain step-by-step how the deque is updated when sliding the window over the array.

Think about how the deque keeps only useful elements for maximum.

Describe why the Sliding Window Maximum problem can be solved in O(n) time using a deque.

Focus on how many times each element enters and leaves the deque.