Next Greater/Smaller Element using a Monotonic Queue

Next greater/smaller element using an array

Before checking out the approach for the next greater/smaller element using a monotonic queue, let’s see the array approach.

The outer loop traverses the array from left to right. The inner loop will compare the current element with all the elements to its right until it finds an element greater (in the next greater element function) / smaller (in the next smaller element function) than the current element. If no such element is present, -1 is printed.
 

Steps:

1. Traverse the array from left to right in the outer loop.
2. Initialize nextGreater and nextSmaller with -1.
3. In the inner loop, traverse the array through the elements at the right of the current element.
4. In the next greater function: if any element greater than the current element is present, the next greater element is obtained.
5. In the next smaller function: if any element smaller than the current element is present, the next smaller element is obtained.

Code:

public class Main {

  // Function to display the next smaller elements
  private static void smallerElement(int[] arr) {
    System.out.println("Next Smaller Element: ");
    for (int i = 0; i < arr.length; i++) {
      int nextSmaller = -1;

      // Find the next smaller element
      for (int j = i + 1; j < arr.length; j++) {

        // Break when the next smaller element is found
        if (arr[i] > arr[j]) {
          nextSmaller = arr[j];
          break;
        }
      }
      System.out.print(nextSmaller + " ");
    }
  }

  // Function to display the next greater elements
  private static void greaterElement(int[] arr) {
    System.out.println("Next Greater Element: ");
    for (int i = 0; i < arr.length; i++) {
      int nextGreater = -1;

      // Find the next greater element
      for (int j = i + 1; j < arr.length; j++) {

        // Break when the next greater element is found
        if (arr[i] < arr[j]) {
          nextGreater = arr[j];
          break;
        }
      }
      System.out.print(nextGreater + " ");
    }
  }

  public static void main(String[] args) {
    int[] arr = new int[] { 2, 1, 4, 3 };
    greaterElement(arr);
    System.out.println();
    smallerElement(arr);
  }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Next Greater Element:
4 4 -1 -1
Next Smaller Element:
1 -1 3 -1

You can also try this code with Online Java Compiler

Run Code

Complexity Analysis: 

• Time Complexity: O(N²) as two nested for loops are used.
• Space Complexity:  O(1) as no extra space is required.

Where "N" is the size of the array.

Next greater/smaller element using a monotonic queue

In this approach, a monotonic queue is used. In this case to find the next greater element, decreasing monotonic queue is used. And in this case, to find the next smaller element, an increasing monotonic queue is used. 

In a decreasing monotonic queue, remove the elements that are smaller than the current array element. Continue the process of removal till the monotonic queue is empty, and the last element is greater than the current element.

In an increasing monotonic queue, remove the elements that are greater than the current array element. Continue to process of removal till the monotonic queue is not empty, and the last element is smaller than the current element.

Steps:

1. Initialize a monotonic queue and array.
2. Traverse the array from the end.
3. Update the monotonic queue as explained above.
4. Add the next greater/ smaller element in the array. If the monotonic queue is empty, i.e., no element is present, then add -1.
5. Add the current element to the monotonic queue.

In this monotonic queue, the elements had to be added and removed from the end. Hence, we can use the Deque Interface of the Java collections framework for the implementation. 
 

Code:

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

  // Function to display the next smaller elements
  private static void smallerElement(int[] arr) {
    Deque<Integer> monotonicQueue = new ArrayDeque<Integer>();
    int nextSmallerElement[] = new int[arr.length];

    System.out.println("Next Smaller Element: ");

    // Traverse from end
    for (int i = arr.length - 1; i >= 0; i--) {
      if (monotonicQueue.size() > 0) {

        // Remove elements that are greater than the current array element
        while (monotonicQueue.size() > 0 && monotonicQueue.peekLast() >= arr[i]) {
          monotonicQueue.pollLast();
        }
      }

      // Add the next smaller element in the array
      nextSmallerElement[i] = monotonicQueue.size() <= 0 ? -1 : monotonicQueue.peekLast();

      // Add the current element to the monotonicQueue
      monotonicQueue.add(arr[i]);
    }
    for (int i = 0; i < arr.length; i++)
      System.out.print(nextSmallerElement[i] + " ");
  }

  // Function to display the next greater elements
  private static void greaterElement(int[] arr) {
    Deque<Integer> monotonicQueue = new ArrayDeque<>();
    int nextGreaterElement[] = new int[arr.length];

    System.out.println("Next Greater Element: ");

    // Traverse from end
    for (int i = arr.length - 1; i >= 0; i--) {
      if (monotonicQueue.size() > 0) {

        // Remove elements that are smaller than the array element
        while (monotonicQueue.size() > 0 && monotonicQueue.peekLast() <= arr[i]) {
          monotonicQueue.pollLast();
        }
      }

      // Add the next greater element in the array
      nextGreaterElement[i] = monotonicQueue.size() <= 0 ? -1 : monotonicQueue.peekLast();

      // Add the current element to the monotonicQueue
      monotonicQueue.addLast(arr[i]);
    }
    for (int i = 0; i < arr.length; i++)
      System.out.print(nextGreaterElement[i] + " ");
  }

  public static void main(String[] args) {
    int[] arr = new int[] { 2, 1, 4, 3 };
    greaterElement(arr);
    System.out.println();
    smallerElement(arr);
  }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Next Greater Element:
4 4 -1 -1
Next Smaller Element:
1 -1 3 -1

You can also try this code with Online Java Compiler

Run Code

Complexity Analysis: 

• Time Complexity: O(N) as only a single traversal is required.
• Space Complexity: O(N) as extra space is required for the monotonic queue and array.

Where "N" is the size of the array.

Frequently Asked Questions

What is a monotonic queue?

A monotonic queue is a variety of queues where the elements are all monotonic decreasing or increasing.

What is the time complexity to add and delete elements in the deque?

The time complexity to add and delete elements in the deque is O(1).

What is a deque?

Deque is a double-ended queue that allows the insertion and removal of elements from the front as well as the rear end.

Conclusion

This blog covered the method to find the next greater/smaller element using a monotonic queue along with the complexity analysis.
 

Recommended Reading:

• Program to Insert an element at the Bottom of the Stack
• Top Array Coding Interview Questions
• Print Stack Elements from Top to Bottom

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To learn more about Data Structures and Algorithms, you can enroll in our course on DSA in Java.