✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-215

Deques 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

Array

  • 4

  • 2

  • 12

  • 3

  • 8

  • 1

Window Size

3

Problem

Find the maximum value in each consecutive window.

Results

WindowMaximum
  • 4

  • 2

  • 12

12

  • 2

  • 12

  • 3

12

  • 12

  • 3

  • 8

12

  • 3

  • 8

  • 1

8

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

OperationDescription

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

Language

Pseudocode

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

OperationComplexity

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

QuestionAnswer

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.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures