Next Greater Node In Linked List

Easy
0/40
Average time to solve is 20m
profile
Contributed by
12 upvotes
Asked in companies
UberAppleFacebook

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2 
2 7 4 3 5 -1
1 7 5 1 9 2 5 1 -1
Sample Output 1 :
7 0 5 5 0
7 9 9 9 0 5 0 0

Explanation for Sample 1 :

For Test case 1 : 

Here for the first node village with ninja of strength 2, a village with a stronger ninja is present with a strength of 7 (which is greater than 2), therefore ans[0] = 7. Similarly ‘ans’ array can be filled with the following values: ans = 7,0,5,5,0

For Test case 2 : 

Here for the first node village with a ninja of strength 1, the village with a stronger ninja is present with a strength of 7 (which is greater than 2), therefore ans[0] = 7, similarly ‘ans’ array can be filled with the following values: ans = 7,9,9,9,0,5,0,0
Sample Input 2 :
1
2 1 5 -1
Sample Output 2 :
5 5 0
Hint

Iterate over the linked list and for each node in the list check whether there exists a ‘nextnode’ with a bigger value.

Approaches (2)
Brute Force

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-

 

  1. We will run a loop for the starting node (head) of the given linked list.
  2. 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.
    1. We will maintain a list (array) ‘ans’ for the final answer initialised by 0 which is required.
    2. 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
  3. The list ‘ans’ will be returned finally.
Time Complexity

O(N^2), where N denotes the number of elements in an linked list.

 

We are visiting all the nodes in the linked list with the help of two nested loops, therefore the time complexity will be O(N^2).

Space Complexity

O(N), where N denotes the number of elements in the linked list.

 

The space complexity due to array/list will be O(N). 

Code Solution
(100% EXP penalty)
Next Greater Node In Linked List
Full screen
Console