Monotonic Queues Decoded: Cracking the Code to Efficient Solutions

Monotonic Queue Algorithms

Definition

Monotonic Queue is a data structure that keeps it’s elements either entirely in non-increasing, or entirely in non-decreasing order.

Non-Decreasing: A sequence (a[1], a[2], ..., a[n]) is non-decreasing if, for every pair of indices i and j (where 1 <= i <= j <= n), it holds that a[i] <= a[j].

Non-Increasing: A sequence is non-increasing if, for every pair of indices i and j (where 1 <= i <= j <= n), it holds that a[i] >= a[j].

Examples:

• Non-Decreasing: (1, 2, 2, 3, 5)
• Non-Increasing: (5, 4, 3, 2, 1)

How to create monotonic decreasing queue in java?

LinkedList<Integer> monoQueue = new LinkedList<>();

How we identify that monotonic queue is applicable in problem?

Following are few main scenarios where monotonic queue is applicable...

Finding Next Greater or Smaller Element:

Monotonic queues are commonly used when you need to find the next greater or smaller element for each element in a sequence.

Sliding Window Problems:Monotonic queues are often used in sliding window problems, where you need to efficiently track information about elements within a moving window.

Maintaining Monotonic Order:

If the problem requires maintaining a monotonic order (either increasing or decreasing) of elements while processing a sequence, a monotonic queue might be useful.

Efficient Element Removal:

Monotonic queues are advantageous when you need to efficiently remove elements from both the front and back of the queue, such as finding the first element larger than the current element.

Example: 

The Daily Temperatures problem is a classic problem in computer science and algorithmic interviews. The problem statement typically goes like this:

Given a list of daily temperatures, where temperatures are represented as an array, you are required to find the next day with a higher temperature for each day. If there is no such day, you can return a special value, say 0 or -1.

Input:

codeTemperatures: [73, 74, 75, 71, 69, 72, 76, 73]

Output:

[1, 1, 4, 2, 1, 1, 0, 0]

Code:

public class DailyTemperaturesMonotonicQueue {

    public static int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] result = new int[n];
        LinkedList<Integer> monoQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            while (!monoQueue.isEmpty() && T[i] > T[monoQueue.peekLast()]) {
                int prevIndex = monoQueue.pollLast();
                result[prevIndex] = i - prevIndex;
            }
            monoQueue.offerLast(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] output = dailyTemperatures(temperatures);

        System.out.println(Arrays.toString(output));
    }
}

That's all in this blog. Will see few more example in part2 of blog till then stay tune and happy learning. 

If you are interested in connecting with me for 1:1 please book a session with me.