Next Greater Node In Linked List

Posted: 15 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem