Problem Description

You have a linked list with n nodes. For each node in this linked list, you need to find the next greater node - which means the first node that appears after it and has a value strictly larger than the current node's value.

The task is to return an array answer where answer[i] contains the value of the next greater node for the i-th node (using 1-based indexing). If a node doesn't have any greater node after it, set answer[i] = 0.

For example, if you have a linked list with values [2, 1, 5]:

• For the first node (value = 2), the next greater node has value 5
• For the second node (value = 1), the next greater node has value 5
• For the third node (value = 5), there is no greater node after it, so the answer is 0

The result would be [5, 5, 0].

The solution approach converts the linked list to an array first, then uses a monotonic stack technique. It traverses the array from right to left, maintaining a stack that stores elements in decreasing order from bottom to top. For each element, it pops smaller or equal elements from the stack until finding a larger one (which becomes the next greater element) or the stack becomes empty (meaning no greater element exists). The current element is then pushed to the stack for processing future elements.

Intuition

The key insight is recognizing that this is a "next greater element" problem, which is a classic pattern that can be efficiently solved using a monotonic stack.

Why do we think of using a stack? When we're at a particular node and looking for the next greater element, we need to remember potential candidates as we traverse. The stack helps us maintain these candidates efficiently.

The crucial observation is that if we traverse from right to left, we can maintain a stack of elements that could potentially be the "next greater" for elements we haven't processed yet. Here's the reasoning:

1. When we're at position i, we only care about elements to its right (positions i+1 and beyond).

2. If we have two elements at positions j and k where j < k, and nums[j] <= nums[k], then nums[j] can never be the answer for any element to the left of position j. Why? Because nums[k] is both larger and closer, making it a better candidate.

3. This means we only need to keep track of elements that form a decreasing sequence when viewed from left to right (or increasing when we process from right to left).

By traversing from right to left and maintaining a monotonically decreasing stack:

• When we encounter a new element, we pop all smaller or equal elements from the stack (they're useless now because the current element blocks them)
• The top of the stack (if it exists) is the next greater element
• We then add the current element to the stack as it might be the answer for elements to its left

This approach ensures we process each element exactly once for pushing and at most once for popping, giving us an efficient O(n) solution.

Learn more about Stack, Linked List and Monotonic Stack patterns.

Solution Approach

The implementation follows a two-step process: first converting the linked list to an array, then applying the monotonic stack technique.

Step 1: Convert Linked List to Array

We traverse the linked list and store all values in an array nums:

nums = []
while head:
    nums.append(head.val)
    head = head.next

This conversion simplifies our problem since we can now access elements by index and know the total length n.

Step 2: Build Answer Using Monotonic Stack

We initialize:

• An empty stack stk to maintain potential "next greater" candidates
• An answer array ans of size n filled with zeros (default value for nodes without a next greater element)

We traverse the array from right to left (i from n-1 to 0):

for i in range(n - 1, -1, -1):
    # Pop elements that can't be the answer
    while stk and stk[-1] <= nums[i]:
        stk.pop()
  
    # If [stack](/problems/stack_intro) has elements, top is the next greater
    if stk:
        ans[i] = stk[-1]
  
    # Add current element for future iterations
    stk.append(nums[i])

How the Stack Works:

1. Popping Phase: We remove all elements from the stack that are less than or equal to nums[i]. These elements cannot be the "next greater" for any element to the left of position i because nums[i] is both closer and at least as large.

2. Answer Recording: After popping, if the stack is not empty, the top element is the smallest element to the right of i that is still greater than nums[i] - this is exactly our answer for position i.

3. Pushing Phase: We push nums[i] onto the stack because it might be the "next greater" element for positions to its left.

The stack maintains a monotonically decreasing sequence from bottom to top throughout the process, ensuring each element is pushed once and popped at most once, resulting in O(n) time complexity with O(n) space complexity.

Example Walkthrough

Let's walk through the solution with a linked list containing values [2, 7, 4, 3, 5].

Step 1: Convert to Array After converting the linked list, we have nums = [2, 7, 4, 3, 5].

Step 2: Process with Monotonic Stack (Right to Left)

Initialize: stk = [], ans = [0, 0, 0, 0, 0]

i = 4 (value = 5):

• Stack is empty, no elements to pop
• Stack empty → ans[4] = 0 (no greater element exists)
• Push 5 onto stack
• State: stk = [5], ans = [0, 0, 0, 0, 0]

i = 3 (value = 3):

• Check stack top: 5 > 3, don't pop
• Stack has elements → ans[3] = 5
• Push 3 onto stack
• State: stk = [5, 3], ans = [0, 0, 0, 5, 0]

i = 2 (value = 4):

• Check stack top: 3 ≤ 4, pop 3
• Check stack top: 5 > 4, don't pop
• Stack has elements → ans[2] = 5
• Push 4 onto stack
• State: stk = [5, 4], ans = [0, 0, 5, 5, 0]

i = 1 (value = 7):

• Check stack top: 4 ≤ 7, pop 4
• Check stack top: 5 ≤ 7, pop 5
• Stack empty → ans[1] = 0 (no greater element exists)
• Push 7 onto stack
• State: stk = [7], ans = [0, 0, 5, 5, 0]

i = 0 (value = 2):

• Check stack top: 7 > 2, don't pop
• Stack has elements → ans[0] = 7
• Push 2 onto stack
• State: stk = [7, 2], ans = [7, 0, 5, 5, 0]

Final Result: [7, 0, 5, 5, 0]

This means:

• Node 0 (value=2) → next greater is 7
• Node 1 (value=7) → no greater element
• Node 2 (value=4) → next greater is 5
• Node 3 (value=3) → next greater is 5
• Node 4 (value=5) → no greater element

The stack maintains decreasing order (from bottom to top) throughout, efficiently tracking potential "next greater" candidates for unprocessed elements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. The algorithm consists of two main phases:

• First, traversing the linked list once to convert it into an array, which takes O(n) time
• Second, iterating through the array backwards once while maintaining a monotonic stack. Although there's a nested while loop for stack operations, each element is pushed and popped from the stack at most once, resulting in amortized O(1) operations per element, giving us O(n) total time

The space complexity is O(n). The algorithm uses:

• An array nums to store all values from the linked list: O(n) space
• A stack stk that in the worst case (strictly increasing sequence) could contain all elements: O(n) space
• An answer array ans of size n: O(n) space
• Total space complexity: O(n) + O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Comparison Operator Correctly

A frequent mistake is using < instead of <= when popping elements from the stack:

Incorrect Code:

while stack and stack[-1] < values[i]:  # Wrong: uses < instead of <=
    stack.pop()

Why This Is Wrong: Using < would keep equal elements in the stack, but we need the strictly greater element. If we keep equal elements, they would incorrectly be reported as "next greater" when they're actually equal.

Example Where It Fails: For linked list [2, 2, 1]:

• Using < would give [2, 0, 0] (incorrect - the first 2 shouldn't point to another 2)
• Using <= correctly gives [0, 0, 0] (correct - no element has a strictly greater element after it)

Solution: Always use <= to ensure equal elements are also popped from the stack.

2. Processing the Array in the Wrong Direction

Another common error is traversing the array from left to right instead of right to left:

Incorrect Approach:

for i in range(n):  # Wrong: iterating left to right
    while stack and stack[-1] <= values[i]:
        stack.pop()
    if stack:
        result[i] = stack[-1]
    stack.append(values[i])

Why This Fails: When traversing left to right, the stack contains elements to the left of the current position, not to the right. This completely breaks the logic since we need to find greater elements that come after the current node.

Solution: Always traverse from right to left (range(n-1, -1, -1)) so the stack contains elements that appear after the current position in the original linked list.

3. Not Initializing the Result Array with Zeros

Incorrect Code:

result = []  # Wrong: empty list instead of initialized with zeros
for i in range(n - 1, -1, -1):
    # ... stack operations ...
    if stack:
        result.append(stack[-1])  # This doesn't maintain correct indexing

Why This Is Wrong: Without pre-initializing with zeros, you'd need complex logic to handle cases where no greater element exists, and maintaining the correct index correspondence becomes difficult.

Solution: Always initialize result = [0] * n to ensure each position has a default value of 0, which naturally handles the case when no greater element exists.