Next Greater Element
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 array. Elements for which no greater element exist, consider next greater element as -1.

Examples:

For any array, rightmost element always has next greater element as -1.
For an array which is sorted in decreasing order, all elements have next greater element as -1.
For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element NGE
4 -- 5
5 -- 25
2 -- 25
25 -- -1
For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.

Element NGE
13 -- -1
7 -- 12
6 -- 12
12 -- -1

Question

Next Greater Element

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 array. Elements for which no greater element exist, consider next greater element as -1.

Examples:

For any array, rightmost element always has next greater element as -1.

For an array which is sorted in decreasing order, all elements have next greater element as -1.

For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.

Element NGE

4 --> 5

5 --> 25

2 --> 25

25 --> -1

For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.

Element NGE

13 --> -1

7 --> 12

6 --> 12

12 --> -1

Accepted Answer

Solved this question using stack and comparing current element of array to top of the stack.

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.

Top Ola Cabs Software Developer interview questions & answers

Popular interview questions of Software Developer