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

Monotonic Queues

A Monotonic Queue is a queue-like data structure that maintains elements in increasing or decreasing order and efficiently supports minimum or maximum queries over a changing window.

Explanation

Overview

A Monotonic Queue is commonly implemented using a deque. It removes elements that can no longer affect future minimum or maximum results, keeping only useful candidates in sorted order.

How it works

Process incoming elements one at a time.; Remove elements from the back while they are dominated by the new element.; Insert the new element at the back.; Remove expired elements from the front when they leave the current window.; The front element represents the current minimum or maximum.

Key concepts

Double-ended queue; Monotonic ordering; Candidate elements; Window expiration; Minimum and maximum queries; Amortized complexity

Types

name: Increasing Monotonic Queue; description: Stores candidate elements in increasing order and is useful for minimum queries.; name: Decreasing Monotonic Queue; description: Stores candidate elements in decreasing order and is useful for maximum queries.

Time complexity

operation: Processing all elements; complexity: O(n) amortized; operation: Insertion; complexity: O(1) amortized; operation: Removal; complexity: O(1) amortized

Space complexity

O(k) for a sliding window of size k.

Example

array: 4; 2; windowSize: 3; problem: Find the maximum in each sliding window of size 3.; results: window: 4; 2; maximum: 12; window: 2; 12; maximum: 12

Example or application

Array

  • 4

  • 2

  • 12

  • 3

  • 8

  • 1

Window Size

3

Problem

Find the maximum in each sliding window of size 3.

Results

WindowMaximum
  • 4

  • 2

  • 12

12

  • 2

  • 12

  • 3

12

  • 12

  • 3

  • 8

12

  • 3

  • 8

  • 1

8

Definition

A Monotonic Queue is commonly implemented using a deque. It removes elements that can no longer affect future minimum or maximum results, keeping only useful candidates in sorted order.

Types

NameDescription

Increasing Monotonic Queue

Stores candidate elements in increasing order and is useful for minimum queries.

Decreasing Monotonic Queue

Stores candidate elements in decreasing order and is useful for maximum queries.

How It Works

  • Process incoming elements one at a time.

  • Remove elements from the back while they are dominated by the new element.

  • Insert the new element at the back.

  • Remove expired elements from the front when they leave the current window.

  • The front element represents the current minimum or maximum.

Implementation

Language

Pseudocode

Code

  • function slidingWindowMaximum(array, k):

  • deque = empty deque

  • result = empty list

  • for i from 0 to length(array) - 1:

  • while deque is not empty and deque.front() <= i - k:

  • deque.removeFront()

  • while deque is not empty and array[deque.back()] <= array[i]:

  • deque.removeBack()

  • deque.addBack(i)

  • if i >= k - 1:

  • result.append(array[deque.front()])

  • return result

Time Complexity

OperationComplexity

Processing all elements

O(n) amortized

Insertion

O(1) amortized

Removal

O(1) amortized

Space Complexity

O(k) for a sliding window of size k.

Key Concepts

  • Double-ended queue

  • Monotonic ordering

  • Candidate elements

  • Window expiration

  • Minimum and maximum queries

  • Amortized complexity

Advantages

  • Efficiently maintains minimum or maximum values in a changing window.

  • Avoids scanning every element of each window.

  • Processes an entire array in linear time for common sliding-window problems.

  • Stores only useful candidate elements.

Limitations

  • The queue must be updated carefully when elements expire.

  • It is designed for specific ordered-query patterns rather than arbitrary queries.

  • Duplicate values require a consistent index-removal policy.

Applications

  • Sliding-window maximum

  • Sliding-window minimum

  • Real-time data analysis

  • Moving range statistics

  • Optimization problems involving bounded windows

Related Topics

  • Deques for Sliding Window Problems

  • Monotonic Stacks

  • Queue Data Structures

  • Sliding Window Algorithms

Practice Questions

QuestionAnswer

What is the main purpose of a Monotonic Queue?

To maintain ordered candidates for efficient minimum or maximum queries.

Which data structure is commonly used to implement it?

A double-ended queue, or deque.

What is the typical total processing time for n elements?

O(n) amortized.

Learning Objectives

  • Explain the central idea and purpose of monotonic queues.

  • Identify the assumptions, inputs, and conditions relevant to monotonic queues.

  • Evaluate an application of monotonic queues 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