Next greater/smaller element using a monotonic queue

Riya
Last Updated: May 13, 2022

Introduction 

A good programmer is the one who can write the most optimized codes. To develop this ability, the knowledge of data structures and algorithms becomes essential. Due to this reason, the knowledge of Data Structures and Algorithms (DSA) is frequently tested in interviews for SDE(Software Development Engineering) roles. The importance of DSA cannot be emphasized enough, mainly if you aim to get placed in product-based companies like Google, Amazon, Microsoft, Adobe, etc. 

 

Check out the blog How To Get Better At DSA For Beginners?

 

This blog will discuss the interview problem: find the Next greater/smaller element using a monotonic queue previously asked in companies like Amazon, Samsung, Zoho, Payu, etc.

Next greater/smaller element using a monotonic queue: Problem Statement

An array of elements is given. The task is to find the next greater and smaller element for each element in the array. If there is no greater or smaller element to the right of the element, then return -1.

 

For example:-

Input:

2 1 4 3

Output:

4  4 -1 -1 // next greater element

1 -1  3 -1 // next smaller element

Explanation:

Next Greater Element

  • 4 is the next greater element after 2.
  • 4 is the next greater element after 1.
  • There is no next greater element after 4, so -1 is printed.
  • There is no next greater element after 3, so -1 is printed.

Next Smaller Element

  • 1 is the next smaller element after 2.
  • There is no smaller element after 1, so -1 is printed.
  • 3 is the next smaller element after 4.
  • There is no smaller element after 3, so -1 is printed.

Recommended: Please try to solve the " Next Smaller Element"  on "CODESTUDIO" first before moving on to the solution. 

Recommended: Please try to solve the " Next Greater Element"  on "CODESTUDIO" first before moving on to the solution. 

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);
  }
}

 

Output:

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

 

Complexity Analysis: 

  • Time Complexity: O(N2) 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 the 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);
  }
}

 

Output:

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

 

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

  1. What is a monotonic queue?

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

 

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

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


3. What is a deque?

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

Key Takeaways

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

Don't stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

Was this article helpful ?
1 upvote