Home › DSA › Advanced Patterns

Introduction to Monotonic Queue Pattern

A monotonic queue is a specialized data structure that maintains elements in a specific order—either increasing or decreasing—as they are processed. Unlike a regular queue, where the order of elements strictly follows the sequence of insertion, a monotonic queue ensures that the elements are arranged in a way that optimizes certain operations, such as finding the minimum or maximum in a sliding window.

The monotonic queue pattern is crucial in solving problems where you need to efficiently manage a sliding window over a list of elements. It allows you to maintain order such that finding the minimum or maximum element within the current window becomes an operation. This efficiency is especially useful in scenarios involving large datasets where brute-force methods would be too slow.

Implementation of Monotonic Increasing Queue

A monotonic queue is typically implemented using a deque (double-ended queue). The deque is chosen because it allows efficient addition and removal of elements from both ends, which is crucial in maintaining the order of elements as new ones are processed.

In the case of a monotonic increasing queue, the elements are maintained in non-decreasing order. This structure is particularly useful for solving problems that require tracking the minimum value within a dynamic range, such as in sliding window problems.

Step-by-Step Algorithm

Initialize an empty deque to store the indices of elements (or the elements themselves, depending on the problem).
Iterate through each element in the array or list.
Maintain Order:
- While the deque is not empty and the current element is smaller than or equal to the element at the back of the deque, remove the back element. This ensures that the deque remains in increasing order.
Add Current Element:
- Append the current element (or its index) to the back of the deque.
Continue to the next element and repeat the process until all elements have been processed.
Return the Queue.

Algorithm Walkthrough

Let's walk through the code step by step with the example array nums = {7, 5, 6, 4, 8} to see how the monotonic increasing queue is built:

Initialization:
- An empty deque deque is created to store elements while maintaining the monotonic increasing order.
Iteration:
- The algorithm iterates through each element in the array nums.
Processing 7 (First Element):
- The deque is empty, so 7 is added directly.
- Deque State: [7]
Processing 5 (Second Element):
- 5 is less than 7, so 7 is removed from the deque to maintain the increasing order.
- 5 is then added to the deque.
- Deque State: [5]
Processing 6 (Third Element):
- 6 is greater than 5, so it is added directly to the deque.
- Deque State: [5, 6]
Processing 4 (Fourth Element):
- 4 is less than 6 and 5, so both 6 and 5 are removed from the deque.
- 4 is then added to the deque.
- Deque State: [4]
Processing 8 (Fifth Element):
- 8 is greater than 4, so it is added directly to the deque.
- Deque State: [4, 8]
Final Output:
- After processing all elements, the final monotonic increasing queue in the deque is [4, 8].

Code

java

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

  // Method to create a monotonic increasing queue
  public Deque<Integer> createMonotonicQueue(int[] nums) {
    // Initialize an empty deque to store the elements
    Deque<Integer> deque = new LinkedList<>();

    // Iterate through each element in the array
    for (int num : nums) {
      // Maintain order in the deque
      // Remove elements from the back if they are greater than or equal to the current element
      while (!deque.isEmpty() && deque.peekLast() >= num) {
        deque.pollLast(); // Remove the back element
      }

      // Add the current element to the back of the deque
      deque.offerLast(num);
    }

    // Return the final deque representing the monotonic increasing queue
    return deque;
  }

  public static void main(String[] args) {
    Solution miq = new Solution();
    int[] nums = { 7, 5, 6, 4, 8 };

    // Create the monotonic increasing queue and print the result
    Deque<Integer> result = miq.createMonotonicQueue(nums);
    System.out.println("Monotonic Increasing Queue: " + result);
  }
}

Complexity Analysis

Time Complexity: . Each element is added and removed from the deque at most once, leading to a linear time complexity.
Space Complexity: . In the worst case, the deque can hold up to n elements if the array is strictly increasing or decreasing.

Implementation of Monotonic Decreasing Queue

In the case of a monotonic decreasing queue, the elements are maintained in non-increasing order. This structure is particularly useful for solving problems that require tracking the maximum value within a dynamic range, such as in sliding window problems.

Step-by-Step Algorithm

Initialize an empty deque to store the indices of elements (or the elements themselves, depending on the problem).
Iterate through each element in the array or list.
Maintain Order:
- While the deque is not empty and the current element is greater than or equal to the element at the back of the deque, remove the back element. This ensures that the deque remains in decreasing order.
Add Current Element:
- Append the current element (or its index) to the back of the deque.
Continue to the next element and repeat the process until all elements have been processed.
Return the Queue.

Algorithm Walkthrough

Let's walk through the code step by step with the example array nums = {7, 5, 6, 4, 8} to see how the monotonic decreasing queue is built:

Initialization:
- An empty deque deque is created to store elements while maintaining the monotonic decreasing order.
Iteration:
- The algorithm iterates through each element in the array nums.
Processing 7 (First Element):
- The deque is empty, so 7 is added directly.
- Deque State: [7]
Processing 5 (Second Element):
- 5 is less than 7, so 5 is added directly to the deque.
- Deque State: [7, 5]
Processing 6 (Third Element):
- 6 is greater than 5, so 5 is removed from the deque to maintain the decreasing order.
- 6 is then added to the deque.
- Deque State: [7, 6]
Processing 4 (Fourth Element):
- 4 is less than 6, so it is added directly to the deque.
- Deque State: [7, 6, 4]
Processing 8 (Fifth Element):
- 8 is greater than all the elements in the deque, so 4, 6, and 7 are removed from the deque.
- 8 is then added to the deque.
- Deque State: [8]
Final Output:
- After processing all elements, the final monotonic decreasing queue in the deque is [8].

Code

java

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

  // Method to create a monotonic decreasing queue
  public Deque<Integer> createMonotonicQueue(int[] nums) {
    // Initialize an empty deque to store the elements
    Deque<Integer> deque = new LinkedList<>();

    // Iterate through each element in the array
    for (int num : nums) {
      // Maintain order in the deque
      // Remove elements from the back if they are smaller than or equal to the current element
      while (!deque.isEmpty() && deque.peekLast() <= num) {
        deque.pollLast(); // Remove the back element
      }

      // Add the current element to the back of the deque
      deque.offerLast(num);
    }

    // Return the final deque representing the monotonic decreasing queue
    return deque;
  }

  public static void main(String[] args) {
    Solution mdq = new Solution();
    int[] nums = { 7, 5, 6, 4, 8 };

    // Create the monotonic decreasing queue and print the result
    Deque<Integer> result = mdq.createMonotonicQueue(nums);
    System.out.println("Monotonic Decreasing Queue: " + result);
  }
}

Complexity Analysis

Time Complexity: . Each element is added and removed from the deque at most once, leading to a linear time complexity.
Space Complexity: . In the worst case, the deque can hold up to n elements if the array is strictly increasing or decreasing.

Common Use Cases

Sliding Window Problems: Used to find the maximum or minimum value in a sliding window, such as the "Sliding Window Maximum" problem.
Range Queries: Quickly queries the minimum or maximum value in a dynamic range.
Optimization Problems: Helps in maintaining optimal values efficiently for operations like minimizing cost or maximizing profit.

Now, let's start solving problems on Monotonic Queue.

🤖 Don't fully get this? Learn it with Claude

Stuck on Introduction to Monotonic Queue Pattern? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Introduction to Monotonic Queue Pattern** (DSA) and want to truly understand it. Explain Introduction to Monotonic Queue Pattern from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Introduction to Monotonic Queue Pattern** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Introduction to Monotonic Queue Pattern** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Introduction to Monotonic Queue Pattern** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Introduction to Counting Pattern Introduction to Simulation Pattern →