Next Greater Element To The Right using stack in Java

Hello Everyone! In this Java tutorial, we are going to discuss the problem of flood fill using ‘n’ no of ways. We are going to use the recursion method to solve this problem.

What is the Next Greater Element To The Right

First under what is the next greater element to the right problem, In this problem have to find a greater element to next to the given array. In another word you have given an array, print the Next Greater Element (NGE) for every detail. The Next extra Element for an element x is the first extra element on the proper aspect of x in the array. Elements for which no extra element exist, do not forget next more detail as -1. The subsequent more factors ought to be published in the same order as entering the array.

  • If an element doesn’t have any greater element the mark -1 for the element.
  • The last condition also applies to the last element of the array.

Java Code for solving Next Greater Element To The Right

import java.io.*;
import java.util.*;

public class Solution {

  public static void main(String[] args) throws Exception {
    Scanner bca= new Scanner(System.in);
    System.out.println("Size of the arrray :- ");
    int n = bca.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = bca.nextInt();
    }

    int[] nge = solve(a);
    display(nge);
  }

  public static int[] solve(int[] arr) {
    int[] nge = new int[arr.length];

    Stack<Integer> st = new Stack<>();

    nge[arr.length - 1] = -1;
    st.push(arr[arr.length - 1]);
    for(int i = arr.length - 2; i >= 0; i--){
      while(st.size() > 0 && arr[i] >= st.peek()){
        st.pop();
      }     
      if(st.size() > 0){
        nge[i] = st.peek();
      } else {
        nge[i] = -1;
      }
      
      st.push(arr[i]);
    }

     StringBuilder sb = new StringBuilder();
     for (int val : a)
     { 
      sb.append(val + "\n");
      }
    System.out.println(sb);
  }

}

Implementation using Stack

  1. If the Stack is empty(which it’s far first of all), then push the element in it.
  2. Then take the following element from the array, evaluate it with the primary poped element from the Stack, if the incoming detail is greater than it’s far the next more element for the pinnacle Stack element.
  3. Similarly evaluate the incoming detail with the next detail in Stack(use pop() method), until we find the primary detail inside the Stack that’s greater than the incoming detail. In that case, we will push the incoming detail into the Stack.
  4. Then select any other detail from the array and repeat Step 2 and three.
  5. In the end, whilst all the array factors had been traversed, for the final elements inside the Stack, we can definitely print -1.

 

Now, run this program see the output.

Input

Size of the array :-5
5
3
8
-2
7

Output

8
8
-1
7
-1

Now, You can understand how to solve greater elements to the right.

Leave a Reply

Your email address will not be published.