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

The task is to find the next greater element for each element in the given array.

Iterate through the array from right to left.
Use a stack to keep track of the next greater element.
Pop elements from the stack until a greater element is found or the stack is empty.
If the stack is empty, there is no greater element, so assign -1.
If a greater element is found, assign it as the next greater element.
Push the current element onto the stack.
Return the list of next greater elements.

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).

Accepted Answer

t= int(input())
for _ in range(t):
    arr = list(map(int,input().split()))
    n = len(arr)
    res = []
    curr = arr[0]
    for i in range(1,n):
        temp = -1
        if (curr

For Example :

Input Format :

Output Format :

Note :

Constraints :

Top Sigmoid Data Engineer interview questions & answers

Popular interview questions of Data Engineer