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.

In this tutorial, I am going to explain two approaches and their time complexities to solve this problem. In the first approach, we’ll see how we can find next greater element using two for loops. And after that we can discuss how we can find next greater element using stack.

Also, I have explained how to find next greater element using stack through video tutorial.

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 Find Next Greater Element in an Array?

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: Find next greater element 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 finding next greater element using stack is O(n).

Explanation:

 

Find Next Greater Element in an Array – Java Code

We have discussed two approaches to find next greater element in an array. Let’s write a java program to find next greater element in an array using stack.

Sorting algorithms and their time complexities

Programming questions on stack –  video tutorial

 

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.