LeetCode 1019 - Next Greater Node In Linked List

The problem asks us to process a singly-linked list and, for each node, determine the value of the next node that has a strictly larger value.

leetcodemediumarraylinked-liststackmonotonic-stack

LeetCode Problem 1019

Difficulty: 🟡 Medium
Topics: Array, Linked List, Stack, Monotonic Stack

Solution

Problem Understanding

The problem asks us to process a singly-linked list and, for each node, determine the value of the next node that has a strictly larger value. Concretely, if the list is [2,1,5], for the first node 2, the next larger node is 5; for the second node 1, the next larger node is also 5; for the last node 5, there is no larger node after it, so the answer is 0. The output is an array of integers where each element corresponds to a node in the original linked list, in the same order as the nodes appear.

The input head is the starting node of a linked list with n nodes, where 1 <= n <= 10^4 and each node's value lies between 1 and 10^9. The constraints imply that the solution must be efficient in both time and space; a naive nested loop approach that checks every node against every subsequent node would be too slow for the upper bound of 10,000 nodes.

Key edge cases include a list with only one node, a list where all nodes are strictly decreasing, or a list where all nodes have the same value. The problem guarantees at least one node in the list, so we do not need to handle an empty list.

Approaches

The brute-force approach iterates over each node in the linked list and, for each node, scans all subsequent nodes to find the first node with a larger value. This approach is correct because it explicitly checks every node that could satisfy the "next greater node" condition. However, it requires O(n^2) time, which is prohibitive for large inputs (up to 10,000 nodes).

The optimal approach leverages the concept of a monotonic stack, which is a stack that keeps track of nodes in decreasing order of value. As we iterate over the linked list, we can maintain a stack of indices for which the next greater node has not been found yet. When we encounter a node with a value larger than the value at the top of the stack, we know we have found the next greater node for that index, and we pop it from the stack and update the answer array. This ensures that each node is pushed and popped at most once, achieving O(n) time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterates over each node and checks all subsequent nodes
Optimal O(n) O(n) Uses monotonic stack to efficiently track nodes without next greater value

Algorithm Walkthrough

  1. Initialize an empty list values and traverse the linked list from head, appending each node's value to values. This transforms the linked list into an array to facilitate index-based access.
  2. Create an array answer of the same length as values, initialized with zeros. This will hold the final result.
  3. Initialize an empty stack stack to keep indices of values for which the next greater node has not yet been found.
  4. Iterate over values with index i and value val. For each val, compare it with the values corresponding to indices on the top of stack.
  5. While the stack is not empty and val is greater than values[stack[-1]], pop the index from the stack and set answer[index] = val. This captures the fact that val is the next greater node for the popped index.
  6. After processing the stack, push the current index i onto stack.
  7. Once the iteration completes, any indices left in stack have no greater node following them, and their corresponding answer values remain 0.
  8. Return answer.

Why it works: The stack invariant is that indices in the stack always correspond to values that have not yet found their next greater node, and their corresponding values are in decreasing order. Each value is processed in constant time with respect to stack operations, guaranteeing that the solution is linear in time.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import List, Optional

class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        values = []
        current = head
        while current:
            values.append(current.val)
            current = current.next
        
        answer = [0] * len(values)
        stack = []
        
        for i, val in enumerate(values):
            while stack and val > values[stack[-1]]:
                index = stack.pop()
                answer[index] = val
            stack.append(i)
        
        return answer

The Python implementation first converts the linked list to a simple array for easier index manipulation. The stack stores indices of values that haven't yet found a next greater node. For each value, we pop indices from the stack when the current value is greater, ensuring we assign the next greater value correctly. Remaining indices in the stack correspond to nodes with no next greater node, which is why answer is initialized to zero.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nextLargerNodes(head *ListNode) []int {
    var values []int
    for current := head; current != nil; current = current.Next {
        values = append(values, current.Val)
    }

    answer := make([]int, len(values))
    var stack []int // store indices

    for i, val := range values {
        for len(stack) > 0 && val > values[stack[len(stack)-1]] {
            index := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[index] = val
        }
        stack = append(stack, i)
    }

    return answer
}

The Go implementation mirrors the Python version. Since Go does not have dynamic arrays in the same way, we use slices for values and stack. Nil checks are not necessary for the loop because the linked list is guaranteed to have at least one node. Integer overflow is not a concern due to the constraints, and slice manipulation handles the stack operations efficiently.

Worked Examples

Example 1: head = [2,1,5]

i val stack answer
0 2 [0] [0,0,0]
1 1 [0,1] [0,0,0]
2 5 pop 1 → answer[1]=5, pop 0 → answer[0]=5 answer=[5,5,0], stack=[2]

Example 2: head = [2,7,4,3,5]

i val stack answer
0 2 [0] [0,0,0,0,0]
1 7 pop 0 → answer[0]=7 answer=[7,0,0,0,0], stack=[1]
2 4 [1,2] [7,0,0,0,0]
3 3 [1,2,3] [7,0,0,0,0]
4 5 pop 3 → answer[3]=5, pop 2 → answer[2]=5 answer=[7,0,5,5,0], stack=[4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is pushed and popped at most once on the stack; traversing the linked list is O(n)
Space O(n) Storing node values in an array and stack of indices, each up to n elements

The algorithm is linear because each node is processed exactly twice in the worst case (once when pushed, once when popped).

Test Cases

# Provided examples
assert Solution().nextLargerNodes(ListNode(2, ListNode(1, ListNode(5)))) == [5,5,0]  # simple increasing
assert Solution().nextLargerNodes(ListNode(2, ListNode(7, ListNode(4, ListNode(3, ListNode(5)))))) == [7,0,5,5,0]  # mixed pattern

# Edge cases
assert Solution().nextLargerNodes(ListNode(1)) == [0]  # single node
assert Solution().nextLargerNodes(ListNode(5, ListNode(4, ListNode(3, ListNode(2, ListNode(1)))))) == [0,0,0,0,0]  # strictly decreasing
assert Solution().nextLargerNodes(ListNode(1, ListNode(1, ListNode(1, ListNode(1))))) == [0,0,0,0]  # all same values

# Larger test case
assert Solution().nextLargerNodes(ListNode(1, ListNode(3, ListNode(2, ListNode(5, ListNode(4)))))) == [3,5,5,0,0]  # mixed increases and decreases

| Test | Why |

|