Find Next Greater Element in an Array – Java Code

Write a java program to find next greater element in an array. Given an input array, find the next greater element for every element of an array.The next greater element x is the first greater element on the right side of x in an array.

For example:

Let’s take an array: [4, 2, 6, 8, 1]

4 => 6 (First next greater element of 4 is 6)
2 => 6 (Next greater element of 2 is 6)
6 => 8 (Next greater element of 6 is 8)
8 => null
1 => null

Find Next Greater Element in an Array

Java Program to Find Next Greater Element

How to Solve this Problem?

i) Method 1: Using two for loops

Subscribe Our Tutorials

Get Latest Updates on Facebook

Using two for loops, For every element iterate on the right side of an array to find the first greater element. Break the loop when the first greater element is found. The time complexity of this approach is O(n2).

 

ii) Method 2: Using stack

1) Initially when a stack is empty. Push the first element in a stack.
2) if arr[i] > stack.top, Pop the element and print the next greater element.
3) Push arr[i] on the stack.
4) Repeat step 2 and 3 until the array is traversed completely.

The time complexity of this approach is O(n).

Explanation:

 

Java Program to Find Next Greater Element in an Array

We have discussed two approaches to find next greater element in an array. Let’s write a java program to print next greater element in an array using a stack. The time complexity of this approach is O(n).

Sorting algorithms and their time complexities

 

Java program to find first Non-repeated character in a string

Java program to check prime number

Java program to check anagram

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.