Monotonic Queue

monotonic-queue: The Ultimate Cheatsheet

1. Detailed Explanation

• What is a monotonic-queue?

A monotonic queue (also sometimes called a deque) is a data structure that maintains its elements in either monotonically increasing or monotonically decreasing order. It supports efficient insertion and deletion from both ends, similar to a standard deque. The key difference is that upon insertion, elements are removed from the back of the queue to maintain the desired monotonicity.

• Why is it important and what kind of problems does it solve?

Monotonic queues are crucial for solving problems involving sliding windows where you need to find the maximum or minimum element within the window efficiently. Specifically, they excel in situations where you need to maintain a sorted list of potential candidates (maximum or minimum) within a moving window. They avoid the need to re-sort the entire window at each step.

• Core concepts, underlying principles, and key terminology.

  • Monotonicity: The property of being either entirely non-increasing or non-decreasing.
  • Deque (Double-Ended Queue): A linear data structure that allows insertion and deletion from both ends. Monotonic queues are typically implemented using deques.
  • Sliding Window: A contiguous sub-sequence of a given sequence that “slides” along the sequence.
  • Head (Front): The beginning of the queue. In a monotonic queue used for finding the maximum, the head will often contain the index of the current maximum element in the window.
  • Tail (Back): The end of the queue. New elements are added to the tail, potentially removing elements to maintain monotonicity.

2. When to Use monotonic-queue (and When Not To)

• Identify problem patterns that suggest monotonic-queue is a good fit.

  • Sliding Window Problems: Any problem that involves a sliding window and asks for the maximum or minimum element within that window.
  • Optimization Problems: Problems where you need to maintain a set of “best” candidates that can be updated efficiently as you iterate through the input.
  • Problems where you need to find the next greater/smaller element in an array: A monotonic stack can be used, which shares the same principles.

• Discuss scenarios where a different data structure or algorithm would be more appropriate.

  • No Sliding Window: If the problem doesn’t involve a sliding window, a monotonic queue is unlikely to be useful.
  • Fixed-size Window, No Need for Max/Min: If you simply need to process each element in a fixed-size window without needing the maximum or minimum, a simple loop or array slicing might suffice.
  • Non-contiguous Subsequences: If you need to find the maximum or minimum of non-contiguous subsequences, dynamic programming or other techniques are more suitable.
  • Small Window Size: If the window size is extremely small (e.g., k=2 or 3), the overhead of maintaining a monotonic queue might outweigh its benefits. A simple linear search within the window might be faster.
  • Constantly Changing Elements: If the elements within the window are constantly changing (not just sliding), a different data structure like a self-balancing binary search tree (e.g., TreeSet in Java) might be more appropriate, though with higher complexity.

3. Core Algorithm / Data Structure Template

Here’s a general template for solving sliding window maximum/minimum problems using a monotonic queue:

1. Initialization:

   • Create a deque (e.g., collections.deque in Python, Deque in Java, std::deque in C++).
   • The deque will store indices of the array elements, not the elements themselves. This is important for removing elements that are outside the current window.

2. Iteration:

   • Iterate through the input array.
   • Maintain Monotonicity (Decreasing for Maximum, Increasing for Minimum):
     • While the deque is not empty and the current element is greater than (for maximum) or less than (for minimum) the element at the back of the deque, remove elements from the back of the deque.
     • This ensures that the deque maintains its monotonic property.
   • Add Current Element’s Index:
     • Add the index of the current element to the back of the deque.
   • Remove Elements Outside the Window:
     • If the index at the front of the deque is outside the current window (i.e., deque[0] < i - k + 1), remove it from the front.
   • Get Maximum/Minimum:
     • The element at the front of the deque is the index of the maximum/minimum element in the current window. Use this index to retrieve the actual element from the array.

3. Result:

   • Store the maximum/minimum values for each window in a result array.

4. Code Implementations (Python, Java, C++)

Python

from collections import deque

def sliding_window_maximum(nums, k):
    """
    Finds the maximum element in each sliding window of size k.

    Args:
        nums: A list of integers.
        k: The size of the sliding window.

    Returns:
        A list of the maximum elements in each sliding window.
    """
    if not nums:
        return []

    result = []
    dq = deque()  # Stores indices
    for i in range(len(nums)):
        # Maintain decreasing order
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)

        # Remove elements outside the window
        if dq[0] < i - k + 1:
            dq.popleft()

        # Add maximum to result when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example usage:
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window_maximum(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

Java

import java.util.Deque;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] slidingWindowMaximum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        List<Integer> resultList = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>(); // Stores indices

        for (int i = 0; i < nums.length; i++) {
            // Maintain decreasing order
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // Remove elements outside the window
            if (deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Add maximum to result when window is full
            if (i >= k - 1) {
                resultList.add(nums[deque.peekFirst()]);
            }
        }

        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = sol.slidingWindowMaximum(nums, k);
        for (int num : result) {
            System.out.print(num + " "); // Output: 3 3 5 5 6 7
        }
        System.out.println();
    }
}

C++

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

vector<int> slidingWindowMaximum(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // Stores indices

    for (int i = 0; i < nums.size(); ++i) {
        // Maintain decreasing order
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // Remove elements outside the window
        if (dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // Add maximum to result when window is full
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = slidingWindowMaximum(nums, k);

    for (int num : result) {
        cout << num << " "; // Output: 3 3 5 5 6 7
    }
    cout << endl;

    return 0;
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity
sliding_window_maximum	O(n)	O(k)
Explanation

• Time Complexity: O(n), where n is the length of the input array. Each element is added to and removed from the deque at most once.
• Space Complexity: O(k), where k is the size of the sliding window. The deque stores at most k elements (indices).

6. Pro Tips, Tricks, and Common Pitfalls

• Store Indices, Not Values: Always store indices in the deque, not the actual values. This allows you to easily check if an element is outside the current window by comparing its index to the window boundaries.
• Monotonicity Direction: Ensure that you’re maintaining the correct monotonicity (increasing or decreasing) based on whether you’re looking for the minimum or maximum.
• Empty Deque: Handle the case where the deque is empty when trying to access the front or back element.
• Window Size Check: Make sure to only add the maximum/minimum to the result after the window has reached its full size (i.e., i >= k - 1).
• Deque Clear: If you are re-using the monotonic queue in a loop, be sure to clear the deque.

7. Classic Problem Examples

Example: Sliding Window Maximum

Description: You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

High-Level Approach:

1. Initialize: Create a deque dq to store indices of nums.
2. Iterate: Iterate through nums from left to right.
3. Maintain Decreasing Order: For each element nums[i], remove elements from the back of dq while nums[dq[-1]] < nums[i]. This ensures that dq stores indices of elements in decreasing order.
4. Add Current Index: Add the current index i to the back of dq.
5. Remove Out-of-Window Elements: If the index at the front of dq (i.e., dq[0]) is outside the current window (i.e., dq[0] < i - k + 1), remove it from the front of dq.
6. Add Maximum to Result: If the window is full (i.e., i >= k - 1), the element at the front of dq is the index of the maximum element in the current window. Add nums[dq[0]] to the result.
7. Return: Return the list of maximums. The code implementations above demonstrate this algorithm.