Java Program to Print Next Greater Element in Array

«
»

This is the Java Program to Print the Next Greatest Element in the Array in Order, Elements with no Greater Elements will have -1 Printed Next to them.

Problem Description

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider next greater element as -1.

Example:

advertisement

For the input array [6, 4, 5, 7], the next greater elements for each element are as follows.

6—->7
4—->5
5—->7
7—->-1

Problem Solution

Create a stack and push the first element of the array onto it. Now for each of the remaining elements, check whether the stack is empty or not. If the stack is not empty, pop an element from the stack, if the element is smaller than the current array element, then print the current element as the next greater element for popped element. Continue the process, either until the stack is empty or the popped element is greater than the current array element. Finally, push the current array element onto the stack. At last, after iterating over the array, pop all the elements of the stack and print -1 as the next greater element for them.

advertisement
advertisement
Program/Source Code

Here is the source code of the Java Program to Print the Next Greatest Element in the Array in Order, Elements with no Greater Elements will have -1 Printed Next to them. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. // Java program to print the next greatest element in the array
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5. import java.util.Stack;
  6.  
  7. public class NextGreater {
  8.     // Method to print the next greatest element
  9.     static void printNextGreatest(int[] array){
  10.         Stack<Integer> stack=new Stack<>();
  11.         stack.push(array[0]);
  12.         int i,x;
  13.         for(i=1;i<array.length;i++){
  14.             if(stack.empty()){
  15.                 stack.push(array[i]);
  16.                 continue;
  17.             }
  18.             while (!stack.empty() && stack.peek()<array[i]){
  19.                x=stack.peek();
  20.                System.out.println(x+"---->"+array[i]);
  21.                stack.pop();
  22.             }
  23.             stack.push(array[i]);
  24.         }
  25.         while(!stack.empty()){
  26.             System.out.println(stack.pop()+"---->"+-1);
  27.         }
  28.     }
  29.     // Main method to read the array
  30.     public static void main(String[] args) {
  31.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  32.         int size;
  33.         System.out.println("Enter the size of the array");
  34.         try {
  35.             size = Integer.parseInt(br.readLine());
  36.         } catch (Exception e) {
  37.             System.out.println("Invalid Input");
  38.             return;
  39.         }
  40.         int[] array = new int[size];
  41.         System.out.println("Enter array elements");
  42.         int i;
  43.         for (i = 0; i < array.length; i++) {
  44.             try {
  45.                 array[i] = Integer.parseInt(br.readLine());
  46.             } catch (Exception e) {
  47.                 System.out.println("Invalid element. Enter it again");
  48.                 i--;
  49.             }
  50.         }
  51.         printNextGreatest(array);
  52.     }
  53. }
Program Explanation

1. In function printNextGreatest(), a new stack is created through the statement Stack stack=new Stack<>()
and the first element of the array is pushed onto the stack.
2. The loop for(i=1;i<array.length;i++) is used to iterate through the array.
3. Firstly, it is checked if the stack is empty if it is then the current array element is added to the stack.
4. The nested loop while (!stack.empty() && stack.peek()<array[i]), checks if the element at the top of the stack is less than the current array element.
5. If it is, then array[i] is the next greater element, for the element at the top of the stack.
6. At the end of each iteration of while loop, the element is popped from the stack.
7. At the end of each iteration of for loop, the current element is pushed onto the stack.
8. Finally, the last while loop is used, to print all the elements having no next greater element.

advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
4
Enter array elements
6
4
5
7
4---->5
5---->7
6---->7
7---->-1
 
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
1---->2
2---->3
3---->4
4---->5
5---->-1

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.