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

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 Bharti Airtel Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Bharti Airtel Software Engineer