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:

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.

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.

```
 
```

// Java program to print the next greatest element in the array

```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
import java.util.Stack;
```
```
 
```
```
public class NextGreater {
```

    // Method to print the next greatest element

    static void printNextGreatest(int[] array){

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

```
        stack.push(array[0]);
```
```
        int i,x;
```
```
        for(i=1;i<array.length;i++){
```
```
            if(stack.empty()){
```
```
                stack.push(array[i]);
```
```
                continue;
```
```
            }
```

            while (!stack.empty() && stack.peek()<array[i]){

```
               x=stack.peek();
```

               System.out.println(x+"---->"+array[i]);

```
               stack.pop();
```
```
            }
```
```
            stack.push(array[i]);
```
```
        }
```
```
        while(!stack.empty()){
```

            System.out.println(stack.pop()+"---->"+-1);

```
        }
```
```
    }
```
```
    // Main method to read the array
```

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("Invalid element. Enter it again");

```
                i--;
```
```
            }
```
```
        }
```
```
        printNextGreatest(array);
```
```
    }
```
```
}
```

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.

Subscribe Now: Java Programs Newsletter | Important Subjects Newsletters

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.

« Prev - Java Program to Find Local Maxima in an Array

» Next - Java Program to Find the Minimum Distance between Array Elements

Related Posts:

Recommended Articles: