Last Updated: 15 Mar, 2021
Next Greater Node In Linked List
Easy
Asked in companies
Ninjas are often known for their superhuman strength and valour. In a given set of linked ninja villages of different clans, their strongest ninjas want to know whether there exists a stronger ninja in the nearest village linked ahead of their village in order to be prepared for threats and enemies.
You are given the villages in the form of a linked list consisting of N integers each integer representing the strength of the strongest ninja in their village. The head of the linked list would be pointing to the strength of the strongest ninja in the first village (which would be the first node).
The nodes in the list can be numbered as "node 1", "node 2" and so on. Each node may have a next larger value (a village with a stronger ninja)
For "node i" , next larger("node i") is the "node j.val" such that j > i and "node j.val" > "node i.val" , and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
Note :
Your task is to return an array of integers answer,
where ans[i] = next_larger(node_{i+1}).
For Example :
Input: 2 - >1 -> 5
Output: ans = [5,5,0]
Here for the first node village, the village with a stronger ninja is present with a strength of 5, therefore ans[0] = 5.
Similarly ans[1] = 5 and since there are no villages after node 3 with stronger ninjas, therefore, ans[2] = 0
Input Format :
The first line of input contains a single integer ‘T’ denoting the number of test cases.
The second line contains single space-separated integers, denoting the elements of the linked list with -1 being the last element denoting the end of the list (or null element).
Output Format :
Return an array of integers answer, where ans[i] = next_larger(node_{i+1}).
Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N <= 5000
1 <= node.val <=10^9
where 'N' is the size of the linked list and 'node.value' is the value of a node.
Time Limit : 1 sec
Approaches
We will iterate through the given linked list of elements (nodes) with the help of two nested loops. Where we will check for every node whether there exists a next node with a value bigger than the value of current node and subsequently build the ‘ans’ list (array) and return it.
The algorithm will be-
- We will run a loop for the starting node (head) of the given linked list.
- From every node we will run a loop and traverse the remaining nodes to check if there exists a node with a bigger value than our current node.
- We will maintain a list (array) ‘ans’ for the final answer initialised by 0 which is required.
- Add the next node’s value if it has a value bigger than the current node otherwise keep traversing linked list ahead until we reach the end of the list
- The list ‘ans’ will be returned finally.
The main observation here is that the above naive approach can be optimized by maintaining a monotonically decreasing stack of elements traversed. If a greater element is found, then append it to the resultant linked list ‘L’ else append 0.
The algorithm will be -
- Push the first node to stack and pick the rest of the nodes sequentially following the below-listed steps in a loop (until the end of the list is reached):
- First, mark the current node as the next node.
- Now, If the stack is not empty, compare the top node value of the stack with the next node value in the list.
- If the next node value is greater than the top node value of the stack then, Pop the top node from the stack and update the stack by pushing the next node value as the next greater element for the popped node.
- Keep popping the node from the stack while the popped node value is smaller than the next node value. The next node will become the next greater element for all such popped node.
- Finally, push the next node in the stack.
- Now, after the loop is over, pop all the node from the stack and print 0 as the next element for them.