Next Greater Element
For a given array/list of integers of size N, print the Next Greater Element(NGE) for every element. The Next Greater Element for an element X is the first element on the right side of X in the array, which is greater than X. If no greater elements exist to the right of X, consider the next greater element as -1.

For example:

For the given array [7, 12, 1, 20] - The next greater element for 7 is 12. - The next greater element for 12 is 20. - The next greater element for 1 is 20. - There is no greater element for 20 on the right side. Output: [12, 20, 20, -1]

Input Format:

The first line of input contains an integer 'N' representing the size of the array/list. The second line of input contains 'N' single space-separated integers representing the elements of the array/list.

Output Format :

The only line of output contains 'N' single space-separated integers representing the Next Greater Element for each element.

Note :

You do not need to print anything explicitly, it has already been taken care of.

Constraints :

1

Question

Next Greater Element

For a given array/list of integers of size N, print the Next Greater Element(NGE) for every element. The Next Greater Element for an element X is the first element on the right side of X in the array, which is greater than X. If no greater elements exist to the right of X, consider the next greater element as -1.

For example:

For the given array [7, 12, 1, 20]

- The next greater element for 7 is 12.
- The next greater element for 12 is 20. 
- The next greater element for 1 is 20. 
- There is no greater element for 20 on the right side.

Output: [12, 20, 20, -1]

Input Format:

The first line of input contains an integer 'N' representing the size of the array/list.

The second line of input contains 'N' single space-separated integers representing the elements of the array/list.

Output Format :

The only line of output contains 'N' single space-separated integers representing the Next Greater Element for each element.

Note :

You do not need to print anything explicitly, it has already been taken care of.

Constraints :

1 <= N <= 10^5
1 <= ARR[i] <= 10^9

Time Limit: 1 sec

Accepted Answer

Brute Force

For every element in the array, we will run a loop on its right side. As soon as we find an element on its right side which is greater than it, we will break the loop, assign it as the NGE of this element, move forward, and do the same for the next element.

Space Complexity: O(1)Explanation:

O(1)

No extra space is used.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where N is the number of elements in the array/list.

For every element, we will be checking nearly every other element in the array, hence time complexity is quadratic.

Accepted Answer

Using Stack

We will use a Stack to keep track of the next greater element and pop as soon as we find an element greater than it.

Here is the complete algorithm:

Create a new array ANS[ ] of the same size as the input array to store the Next Greater Elements.
Declare a stack that will have Next Greater Element as its top element.
Traverse the array in reverse order and for every element at i-th index
- Pop the stack until the current element is greater than the top element of the stack
- Update ANS[i] with the top element of the stack or -1 if the stack is empty.
- Push the current element onto the stack.
Return ANS[ ]

Space Complexity: O(n)Explanation:

O(N), Where N is the number of elements in the array.

In the worst case, Stack can hold all the elements of the array, hence space complexity is also linear.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of elements in the array.

At first glance, it looks like an O(N^2) complexity solution because we’re going through the previous elements again.

When the array is given in decreasing order, then for every element in the array

We push it onto the stack
It gets popped at the next iteration by a greater element

Hence, in the worst case, every element in the array gets pushed and popped into the stack at most once. Thus, the time complexity is linear.

For example:

Input Format:

Output Format :

Note :

Constraints :

Top Groww Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Groww Software Developer