concept · INFO-CS-ADS-215Deques for Sliding Window Problems
A deque, or double-ended queue, supports insertion and removal at both ends and is especially useful for solving sliding-window problems efficiently.
Explanation
Overview
A deque is a linear data structure that allows elements to be inserted or removed from both the front and the back. In sliding-window algorithms, it can maintain useful candidate elements while the window moves through an array or sequence.
Key concepts
Double-ended queue; Sliding window; Index tracking; Window boundaries; Candidate elimination; Monotonic ordering
Time complexity
operation: Sliding-window processing; complexity: O(n) amortized; operation: Deque insertion; complexity: O(1); operation: Deque removal; complexity: O(1)
Space complexity
O(k) for a deque holding at most k candidate indices.
Example
array: 4; 2; windowSize: 3; problem: Find the maximum value in each consecutive window.; results: window: 4; 2; maximum: 12; window: 2; 12; maximum: 12; explanation: The deque stores indices of useful candidates in decreasing order of their corresponding values. The front always identifies the maximum of the current window.
Applications
Sliding-window maximum and minimum; Finding maximum values in fixed-size intervals; Window-based dynamic programming optimization; Real-time sequence processing; Maintaining candidates in bounded-range problems
Advantages
Supports operations at both ends in constant time.; Can solve sliding-window maximum and minimum problems in O(n) time.; Avoids repeatedly sorting or scanning each window.; Can be used for both increasing and decreasing candidate sequences.
Example or application
Problem
Find the maximum value in each consecutive window.
Explanation
The deque stores indices of useful candidates in decreasing order of their corresponding values. The front always identifies the maximum of the current window.
Definition
A deque is a linear data structure that allows elements to be inserted or removed from both the front and the back. In sliding-window algorithms, it can maintain useful candidate elements while the window moves through an array or sequence.
Core Operations
| Operation | Description |
|---|
pushFront | Inserts an element at the front. |
pushBack | Inserts an element at the back. |
popFront | Removes the front element. |
popBack | Removes the back element. |
front | Reads the front element without removing it. |
back | Reads the back element without removing it. |
Sliding Window Technique
Maintain a deque of indices rather than only storing values.
Remove indices that have moved outside the current window.
Remove dominated indices from the back.
Insert the current index.
Read the front index to obtain the current window's minimum or maximum.
Implementation
Code
function maxSlidingWindow(array, k):
deque = empty deque
answer = empty list
for i from 0 to n - 1:
if deque is not empty and deque.front() <= i - k:
deque.popFront()
while deque is not empty and array[deque.back()] <= array[i]:
deque.popBack()
deque.pushBack(i)
if i >= k - 1:
answer.append(array[deque.front()])
return answer
Time Complexity
| Operation | Complexity |
|---|
Sliding-window processing | O(n) amortized |
Deque insertion | O(1) |
Deque removal | O(1) |
Space Complexity
O(k) for a deque holding at most k candidate indices.
Key Concepts
Double-ended queue
Sliding window
Index tracking
Window boundaries
Candidate elimination
Monotonic ordering
Advantages
Supports operations at both ends in constant time.
Can solve sliding-window maximum and minimum problems in O(n) time.
Avoids repeatedly sorting or scanning each window.
Can be used for both increasing and decreasing candidate sequences.
Limitations
The algorithm requires careful handling of window boundaries.
Storing indices is generally necessary to detect expired elements.
A deque alone does not automatically provide sliding-window maximum or minimum; the correct ordering rules must be implemented.
Applications
Sliding-window maximum and minimum
Finding maximum values in fixed-size intervals
Window-based dynamic programming optimization
Real-time sequence processing
Maintaining candidates in bounded-range problems
Related Topics
Monotonic Queues
Monotonic Stacks
Sliding Window Technique
Queue Data Structures
Practice Questions
| Question | Answer |
|---|
What does deque stand for? | Double-ended queue. |
Why are indices stored in sliding-window deques? | They make it possible to identify and remove elements that have expired from the window. |
What is the typical complexity of finding all sliding-window maximums using a monotonic deque? | O(n) total time. |
Learning Objectives
Explain the central idea and purpose of deques for sliding window problems.
Identify the assumptions, inputs, and conditions relevant to deques for sliding window problems.
Evaluate an application of deques for sliding window problems for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
Suggest a correction or source · More in Algorithms & Data Structures