Jobs

Interviews

Discussions

Next Greater Node In Linked List

Medium

Asked by:

27 views

Topics:

Linked ListsStacksArrays

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the i^th node (1-indexed). If the i^th node does not have a next greater node, set answer[i] = 0.

Example 1:

Input: head = [2,1,5]
Output: [5,5,0]

Example 2:

Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]

Constraints:

The number of nodes in the list is n.
1 <= n <= 10⁴
1 <= Node.val <= 10⁹

Try coding it in LeetCode

Next Greater Node In Linked List

Medium

Asked by:

27 views

Topics:

Linked ListsStacksArrays

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the i^th node (1-indexed). If the i^th node does not have a next greater node, set answer[i] = 0.

Example 1:

Input: head = [2,1,5]
Output: [5,5,0]

Example 2:

Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]

Constraints:

The number of nodes in the list is n.
1 <= n <= 10⁴
1 <= Node.val <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the linked list?
What is the range of values stored in the nodes of the linked list? Can they be negative or zero?
If a node doesn't have a next greater node, should the corresponding value in the output array be 0, as stated, or some other default value?
Is the linked list singly or doubly linked? (While this might seem obvious given the problem statement, confirming assumptions is important)
Should the output array maintain the exact same order as the nodes appear in the linked list?

Brute Force Solution

Approach

We need to find, for each item in the list, the first item that comes later in the list and is bigger. The brute force method just checks every possible later item for each item in the list to see if it's bigger.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
For the current item, look at every item that comes after it, one by one.
For each of those later items, check if it's bigger than the current item.
If you find a later item that is bigger, remember that item, and stop looking at the remaining items for the current item.
If you go through all the later items and don't find anything bigger, remember that there is no bigger item later in the list.
Move to the next item in the list and repeat the process, checking all items that come after it.
Do this until you've gone through the whole list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def next_larger_nodes_brute_force(head):
    values = []
    current_node = head
    while current_node:
        values.append(current_node.val)
        current_node = current_node.next

    result = [0] * len(values)

    for i in range(len(values)):
        # Need to find the next greater element for each node
        for j in range(i + 1, len(values)):
            # Check all subsequent nodes
            if values[j] > values[i]:
                result[i] = values[j]
                break

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the linked list. For each node, it then iterates through the remaining nodes in the list to find the next greater node. In the worst case, for each of the n nodes, we might have to traverse almost the entire rest of the list, leading to approximately n * (n-1) / 2 comparisons. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The brute force approach described requires us to store the results in an array. For each node in the linked list of size N, we will have a corresponding entry in the result array to store the next greater node value. Thus, we need an array of size N to store the results. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

To find the next greater node, we'll use a special tool to keep track of promising candidates for the next biggest value. This tool helps us efficiently skip over smaller values and find the answer quickly as we go through the list.

Here's how the algorithm would work step-by-step:

Think of having a special notepad to remember potentially 'bigger' values we've seen so far, but haven't found their 'next bigger' node yet.
Go through the list, node by node, from the beginning to the end.
For each node, compare its value to the values on our notepad, starting with the most recent one.
If the current node's value is bigger than the value on the notepad, we've found the 'next bigger' node for the notepad's value! Note it down.
Keep removing smaller values from the notepad, as the current value is now the 'next bigger' node for all those smaller values.
If the current node's value isn't bigger than any of the values on our notepad, then add the current node's value to our notepad. It might be the 'next bigger' node for future nodes.
At the end, any values still on our notepad didn't have a 'next bigger' node in the list, so their answer is zero.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def next_larger_nodes(head):
    result_list = []
    current_node = head
    while current_node:
        result_list.append(current_node.value)
        current_node = current_node.next_node

    answer = [0] * len(result_list)
    stack = []

    for i in range(len(result_list)): 
        #Process stack for values less than current
        while stack and result_list[stack[-1]] < result_list[i]:
            index = stack.pop()
            answer[index] = result_list[i]

        # Store current index in stack
        stack.append(i)

    return answer

Big(O) Analysis

Time Complexity

O(n) – We iterate through the linked list of n nodes once. Within this iteration, while we compare the current node's value with the stack, each element is pushed and popped from the stack at most once. The stack operations contribute at most O(n) operations across all iterations. Therefore, the overall time complexity is dominated by the single pass through the list, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a stack (the 'notepad') to store node values. In the worst-case scenario, where the linked list is in descending order, all node values will be pushed onto the stack before any are popped. This means the stack can potentially hold N elements, where N is the number of nodes in the linked list. Additionally, an array of size N is used to store the results. Therefore, the auxiliary space is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty linked list	Return an empty array immediately since there are no nodes to process.
Linked list with only one node	Return an array containing only 0, as a single node cannot have a next greater node.
Linked list where all nodes have the same value	Return an array of the same size as the linked list, filled with zeros because no node will have a strictly greater value than any subsequent node.
Linked list with values in strictly decreasing order	Return an array of the same size as the linked list, filled with zeros, because no node will have a greater value than any subsequent node.
Large linked list (scalability)	The stack-based approach should handle large lists efficiently due to its linear time complexity, O(n).
Linked list containing duplicate values	The algorithm correctly identifies the next greater element regardless of duplicate values, using the stack to track potential next greater elements in order.
Linked list with negative values	The comparison operation works correctly with negative numbers, finding the next greater value regardless of sign.
Linked list with very large integer values that may cause integer overflow in some languages	Ensure the language used can handle the range of possible node values to prevent integer overflow during comparison or when creating the result array.

Empty linked list

How to Handle:

Return an empty array immediately since there are no nodes to process.

Linked list with only one node

How to Handle:

Return an array containing only 0, as a single node cannot have a next greater node.

Linked list where all nodes have the same value

How to Handle:

Return an array of the same size as the linked list, filled with zeros because no node will have a strictly greater value than any subsequent node.

Linked list with values in strictly decreasing order

How to Handle:

Return an array of the same size as the linked list, filled with zeros, because no node will have a greater value than any subsequent node.

Large linked list (scalability)

How to Handle:

The stack-based approach should handle large lists efficiently due to its linear time complexity, O(n).

Linked list containing duplicate values

How to Handle:

The algorithm correctly identifies the *next* greater element regardless of duplicate values, using the stack to track potential next greater elements in order.

Linked list with negative values

How to Handle:

The comparison operation works correctly with negative numbers, finding the next greater value regardless of sign.

Linked list with very large integer values that may cause integer overflow in some languages

How to Handle:

Ensure the language used can handle the range of possible node values to prevent integer overflow during comparison or when creating the result array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the linked list?
What is the range of values stored in the nodes of the linked list? Can they be negative or zero?
If a node doesn't have a next greater node, should the corresponding value in the output array be 0, as stated, or some other default value?
Is the linked list singly or doubly linked? (While this might seem obvious given the problem statement, confirming assumptions is important)
Should the output array maintain the exact same order as the nodes appear in the linked list?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
For the current item, look at every item that comes after it, one by one.
For each of those later items, check if it's bigger than the current item.
If you find a later item that is bigger, remember that item, and stop looking at the remaining items for the current item.
If you go through all the later items and don't find anything bigger, remember that there is no bigger item later in the list.
Move to the next item in the list and repeat the process, checking all items that come after it.
Do this until you've gone through the whole list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def next_larger_nodes_brute_force(head):
    values = []
    current_node = head
    while current_node:
        values.append(current_node.val)
        current_node = current_node.next

    result = [0] * len(values)

    for i in range(len(values)):
        # Need to find the next greater element for each node
        for j in range(i + 1, len(values)):
            # Check all subsequent nodes
            if values[j] > values[i]:
                result[i] = values[j]
                break

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of having a special notepad to remember potentially 'bigger' values we've seen so far, but haven't found their 'next bigger' node yet.
Go through the list, node by node, from the beginning to the end.
For each node, compare its value to the values on our notepad, starting with the most recent one.
If the current node's value is bigger than the value on the notepad, we've found the 'next bigger' node for the notepad's value! Note it down.
Keep removing smaller values from the notepad, as the current value is now the 'next bigger' node for all those smaller values.
If the current node's value isn't bigger than any of the values on our notepad, then add the current node's value to our notepad. It might be the 'next bigger' node for future nodes.
At the end, any values still on our notepad didn't have a 'next bigger' node in the list, so their answer is zero.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def next_larger_nodes(head):
    result_list = []
    current_node = head
    while current_node:
        result_list.append(current_node.value)
        current_node = current_node.next_node

    answer = [0] * len(result_list)
    stack = []

    for i in range(len(result_list)): 
        #Process stack for values less than current
        while stack and result_list[stack[-1]] < result_list[i]:
            index = stack.pop()
            answer[index] = result_list[i]

        # Store current index in stack
        stack.append(i)

    return answer

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list	Return an empty array immediately since there are no nodes to process.
Linked list with only one node	Return an array containing only 0, as a single node cannot have a next greater node.
Linked list where all nodes have the same value	Return an array of the same size as the linked list, filled with zeros because no node will have a strictly greater value than any subsequent node.
Linked list with values in strictly decreasing order	Return an array of the same size as the linked list, filled with zeros, because no node will have a greater value than any subsequent node.
Large linked list (scalability)	The stack-based approach should handle large lists efficiently due to its linear time complexity, O(n).
Linked list containing duplicate values	The algorithm correctly identifies the next greater element regardless of duplicate values, using the stack to track potential next greater elements in order.
Linked list with negative values	The comparison operation works correctly with negative numbers, finding the next greater value regardless of sign.
Linked list with very large integer values that may cause integer overflow in some languages	Ensure the language used can handle the range of possible node values to prevent integer overflow during comparison or when creating the result array.

Empty linked list

How to Handle:

Return an empty array immediately since there are no nodes to process.

Linked list with only one node

How to Handle:

Return an array containing only 0, as a single node cannot have a next greater node.

Linked list where all nodes have the same value

How to Handle:

Return an array of the same size as the linked list, filled with zeros because no node will have a strictly greater value than any subsequent node.

Linked list with values in strictly decreasing order

How to Handle:

Return an array of the same size as the linked list, filled with zeros, because no node will have a greater value than any subsequent node.

Large linked list (scalability)

How to Handle:

The stack-based approach should handle large lists efficiently due to its linear time complexity, O(n).

Linked list containing duplicate values

How to Handle:

The algorithm correctly identifies the *next* greater element regardless of duplicate values, using the stack to track potential next greater elements in order.

Linked list with negative values

How to Handle:

The comparison operation works correctly with negative numbers, finding the next greater value regardless of sign.

Linked list with very large integer values that may cause integer overflow in some languages

How to Handle:

Ensure the language used can handle the range of possible node values to prevent integer overflow during comparison or when creating the result array.