# Find the next greater element for every array element

Given an integer array, find the next greater element for every array element. The next greater element of a number `x` is the first greater number to the right of `x` in the array.

In other words, for each element `A[i]` in the array `A`, find an element `A[j]` such that `j > i` and `A[j] > A[i]` and the value of `j` should be as minimum as possible. If the next greater element doesn’t exist in the array for any element, consider it `-1`.

For example,

Input:  [2, 7, 3, 5, 4, 6, 8]
Output: [7, 8, 5, 6, 6, 8, -1]

Input:  [5, 4, 3, 2, 1]
Output: [-1, -1, -1, -1, -1]

Note that the next greater element for the last array element is always -1.

Practice this problem

## 1. Brute-Force Approach

The idea is to use two nested loops. The outer loop takes each array element from left to right. The inner loop considers all elements to the “right” of the element picked by the outer loop. Terminate the inner loop as soon as the first larger element is found, which would be the next greater element for the element picked by the outer loop.

The time complexity of this approach is O(n2), where `n` is the size of the input. Following is the implementation in C, Java, and Python based on the above idea:

Output:

7 8 5 6 6 8 -1

Output:

7 8 5 6 6 8 -1

Output:

7 8 5 6 6 8 -1

## 2. Using Stack

The time complexity can be easily reduced to linear by using extra space. The idea is to use the stack data structure.

• For each element `x` in the array, pop all elements from the stack smaller than `x`, and set their next greater element to `x`.
• Loop till we have a greater element on top of the stack or stack becomes empty. Then push the current element `x` on top of the stack.
• Repeat the process for every array element.

Following is the C++, Java, and Python program that demonstrates this algorithm. Note that we are pushing indexes into the stack instead of the actual elements. Now the next greater element can be set for the popped elements using their index.

Output:

7 8 5 6 6 8 -1

## Java

Output:

[7, 8, 5, 6, 6, 8, -1]

## Python

Output:

[7, 8, 5, 6, 6, 8, -1]

Here’s another stack-based solution where elements are processed from right to left in the array.

• For each element `x` in the array, loop, till we have a greater element on top of the stack or stack, becomes empty.
• Once the stack contains a greater element on the top, set it as the next greater element of `x` and push `x` on top of the stack. If the stack becomes empty, set the next greater `x` as `-1`.
• Repeat the process for every array element.

Following is the C++, Java, and Python program that demonstrates this algorithm:

Output:

7 8 5 6 6 8 -1

## Java

Output:

[7, 8, 5, 6, 6, 8, -1]

## Python

Output:

[7, 8, 5, 6, 6, 8, -1]

The time complexity of both stack-based solutions is O(n) since every element is pushed and popped at most once to the stack. The auxiliary space used is O(n) for the stack.

Exercise: Extend the solution for a circular array to search circularly to find the next greater element.

Rate this post

Average rating 4.83/5. Vote count: 146

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?