Next Greater Element
You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains an integer N, representing the length of the input array(ARR). The second line contains N single space-separated integers representing elements of the array arr.

Output Format :

For each test case, print a list of integers each representing the NGE(next greater element) of each element of the given array in a single line.

Note :

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Next Greater Element

You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains an integer N, representing the length of the input array(ARR).

The second line contains N single space-separated integers representing elements of the array arr.

Output Format :

For each test case, print a list of integers each representing the NGE(next greater element) of each element of the given array in a single line.

Note :

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints :

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

Time Limit: 1sec

Accepted Answer

Approach 1 (Naive Solution) :

1) Use two loops: The outer loop picks all the elements one by one.
2) The inner loop looks for the first greater element for the element picked by the outer loop.
3) If a greater element is found then that element is printed as next, otherwise, -1 is printed.

TC : O(N^2), where N=size of the array
SC : O(1)

Approach 2 (Using Stack) :

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow the following steps in loop.
2.1) Mark the current element as next.
2.2) If stack is not empty, compare top element of stack with next.
2.3) If next is greater than the top element, Pop element from stack. next is the next greater element for
the popped element.
2.4) Keep popping from the stack while the popped element is smaller than next. next becomes the next
greater element for all such popped elements.
3) Finally, push the next in the stack.
4) After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

TC : O(N), where N=size of the array
SC : O(N)

Accepted Answer

Brute Force

Initialise an array ans of length N to store the next greater number of arr[i] at index i.
Traverse the given array and for every element at index I
- Initialise a variable next to -1.
- Run a loop from i+1 to N, and check whether the current element is greater than arr[i] then update the next to the current element and break the loop.
- Store next at ans[i].
Return ans array.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, only a constant extra space is required.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given array.

In the worst case, we will be searching for the next greater element of each element. For searching the next greater element in arr it can take O(N) time, thus total time would be O(N^2).

Accepted Answer

Optimal Approach

Initialise an array ans of length N to store the next greater number of arr[i] at index i.
Create a stack of type integer, where we will store the smaller element at the top.
Traverse the array from backwards, because when we will arrive at a certain index its next greater element will be already in the stack and we can easily get this element.
For every element at index I,
- We will pop the elements from the stack till we get the greater element on top of the stack from the current element and that element will be the answer for the current element.
- If the stack gets empty while doing the pop operation then the answer would be -1.
- Store the next greater element in the array and.
- Push the current element of the array into the stack.
Finally, return the array ans.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the given array.

In the worst case, all the elements can be in the stack.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the given array.

In the worst case, we will be pushing and popping all the elements into the stack only once. Thus complexity would be O(N).

For Example :

Input Format :

Output Format :

Note :

Constraints :

Top JPMorgan Chase & Co. Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in JPMorgan Chase & Co. Software Developer