Left Short

Easy
0/40
Average time to solve is 50m
profile
Contributed by
26 upvotes
Asked in companies
DirectiD.E.Shaw

Problem statement

You are given a Singly Linked List of integers. Modify the linked list by removing the nodes from the list that have a greater valued node on their adjacent left in the given linked list.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of the input contains 'L' space-separated integers denoting the elements of the singly linked list terminated by -1.

Hence, -1 would never be a list element.
Output Format: 
Print the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
0 <= L <= 5 * 10^5
-10^9 <= node.data <= 10^9 and data != -1

Where 'L' is the number of nodes in the Linked-List.

Time Limit : 1 sec
Sample Input 1:
10 14 6 80 55 56 77 -1
Sample Output 1:
10 14 80 56 77 -1
Explanation For The Sample Output 1:
For the given linked list, nodes with the values 6 and 55 have a greater valued node to their left (14 and 80 respectively). 

Thus, we remove these 2 nodes from the linked list and get the modified list as shown in the output.

Note that the node with the value 56 should not be deleted as its left adjacent node has the value 55 which is not greater than 56.
Sample Input 2:
80 70 60 50 -1
Sample Output 2:
80 -1
Explanation For The Sample Output 2:
For the given linked list, nodes with the values 70, 60, and 50 have a greater valued node to their left (80, 70, and 60 respectively). 

Thus, we remove these 3 nodes from the linked list and get the modified list as shown in the output.
Hint

Try to solve the problem by storing the value of the last deleted node.

Approaches (2)
Intuitive Solution

We use a variable ‘DELETED_VALUE’ to keep track of the value of the last node deleted. This variable is initialized with the value -1 as -1 can never be a list element. 

 

If ‘DELETED_VALUE’ is not equal to -1, this means that we have just deleted a node and we need to compare the value of the next node with ‘DELETED_VALUE’. We iterate through the linked list checking if the value of the next node is less than the value of the current node. Thus, the following situations arise :

 

  1. The value of the next node is less than the value of the current node and ‘DELETED_VALUE’ = -1 : Set ‘DELETED_VALUE’ to the value of the next node and delete the next node.
  2. ‘DELETED_VALUE’ != -1 and value of the next node is less than ‘DELETED_VALUE’ : Set deletedValue to the value of the next node and delete the next node.
  3. In all the other cases, set ‘DELETED_VALUE’ to -1 and move to the next node.
Time Complexity

O(L), where ‘L’ is the number of nodes in the linked list.

 

It takes O(L) time to traverse through the entire list. Also, deletion of a node takes O(1) time. Hence the overall complexity is O(L).

Space Complexity

O(1)

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Left Short
Full screen
Console