1019. Next Greater Node In Linked List

MediumStackArrayLinked ListMonotonic Stack
Leetcode Link

Problem Description

In this problem, we are provided with the head of a singly linked list, which contains n nodes. Each node in the list contains a value, and we are tasked with finding the value of the next greater node for each node in the list. This means for each node in the list, we need to find the first node that appears after it whose value is strictly larger than the value of the current node.

The output of the problem should be an array of integers, where each entry corresponds to the value of the next greater node. Specifically, answer[i] would contain the value of the next greater node for the i-th node in the list (the list is 1-indexed). If a node does not have a next greater node, we should set answer[i] to 0.

To illustrate with an example, let's say we have a linked list 2 -> 1 -> 5. The next greater node for the first node (2) is 5, since 5 is the next node with a value greater than 2. The second node (1) has a next greater node (5) as well. However, the third node (5) doesn't have a next greater node, so its corresponding output would be 0. Hence, the answer would be [5, 5, 0].

Intuition

To arrive at the solution, we analyze the requirements. We need to find the next greater value for each node, and this gives us a hint that we should look at each node from a reverse perspective. If we traverse from the end of the list to the beginning, we can keep track of the greater values we have seen so far, which can help us determine if there's a greater next node.

The solution uses a "stack" data structure to maintain a collection of the greater values we've encountered as we iterate in reverse. At each node, we examine the stack:

  1. We remove from the stack all the elements that are less than or equal to the current node's value, because they will not be the "next greater node" for any of the following elements.
  2. If the stack still has elements after this operation, the top of the stack represents the next greater value for the current node.
  3. We record this value in the answer array.
  4. We then add the current node's value onto the stack to be a potential "next greater node" for the preceding nodes.
  5. Finally, we proceed to the next node (which is actually the previous list node, as we are going in reverse).

By performing these steps for each node, we leverage the stack to keep track of potential "next greater nodes" for each element and efficiently compute the result in a single reverse pass through the list.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which data structure is used in a depth first search?

Solution Approach

The solution involves a technique known as Monotonic Stack. The stack is used to keep the elements in a sorted manner so that for any given element, we can quickly find the next greater element.

Let's break down the implementation step-by-step:

  1. First, we convert the linked list into an array nums to enable easy reverse traversal and to avoid dealing with list node pointers. This is done using a simple while loop that iterates through the linked list and appends each value to nums.
1nums = []
2while head:
3    nums.append(head.val)
4    head = head.next
  1. We initialize a stack stk that will store values from the list in a decreasing order. This is crucial for the monotonic stack pattern to work. Additionally, we initialize the answer array ans with the same length as nums and fill it with zeros.
1stk = []
2ans = [0] * len(nums)
  1. We iterate through the nums list in reverse order using a for loop, starting from the last element down to the first. This enables us to consider the "next" elements before the current element, which makes determining the next greater node possible.
1for i in range(len(nums) - 1, -1, -1):
2    ...
  1. Inside the loop, while the stack is not empty and the value at the top of the stack is less than or equal to nums[i], we pop elements from the stack. This is done to maintain the monotonic decreasing order of the stack.
1while stk and stk[-1] <= nums[i]:
2    stk.pop()
  1. After cleaning the top of the stack, if the stack is not empty, the new top is guaranteed to be the next greater element for nums[i] because of the property of the monotonic stack. We record this value in the ans array at the corresponding index.
1if stk:
2    ans[i] = stk[-1]
  1. Finally, we push nums[i] onto the stack. This is because nums[i] could be the next greater element for the previous nodes in the original list.
1stk.append(nums[i])
  1. After the loop completes, ans contains all the next greater values for each node.

The overall complexity of the solution is O(N), where N is the number of nodes in the list because each element is pushed onto and popped from the stack at most once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's illustrate the solution approach using a small example of a linked list: 3 -> 2 -> 1 -> 5.

  1. Convert Linked List to Array:

    • Initialize nums as an empty list.
    • Traverse the linked list: nums = [3, 2, 1, 5].

  2. Initializations:

    • Initialize the stack stk as an empty list and the answer list ans as [0, 0, 0, 0] (equal in length to nums).

  3. Iterate in Reverse:

    • Start from the end of nums: index i = 3 (value = 5).
    • Stack stk is empty, so add nums[3] to stk: stk = [5].

  4. Reverse iteration to i = 2 (value = 1):

    • Stack stk is [5]. Top (5) is greater than nums[2] (1), so ans[2] = 5.
    • Push nums[2] onto the stack: stk = [5, 1].

  5. Reverse iteration to i = 1 (value = 2):

    • Stack stk is [5, 1]. Pop top (1) since it's not greater than nums[1] (2).
    • Now stk = [5]. Top (5) is greater than nums[1] (2), so ans[1] = 5.
    • Push nums[1] onto the stack: stk = [5, 2].

  6. Reverse iteration to i = 0 (value = 3):

    • Stack stk is [5, 2]. Pop top (2) since it's not greater than nums[0] (3).
    • Now stk = [5]. Top (5) is greater than nums[0] (3), so ans[0] = 5.
    • Push nums[0] onto the stack: stk = [5, 3].

  7. With the iteration complete, the ans list is [5, 5, 5, 0], which corresponds to the next greater values for each node in the list: [3, 2, 1, 5].

Hence, for the linked list 3 -> 2 -> 1 -> 5, the output array indicating the next greater node values is [5, 5, 5, 0].

Solution Implementation

1# Class definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
9        # Convert the linked list into an array to work with indices.
10        valuesList = []
11        while head:
12            valuesList.append(head.val)  # Add node's value into the valuesList
13            head = head.next             # Move to the next node
14      
15        # Stack to keep track of the next larger element
16        stack = []
17      
18        # Length of the linked list or the valuesList
19        n = len(valuesList)
20      
21        # Initialize an answer list of size 'n' with default value of 0
22        answer = [0] * n
23      
24        # Iterate over the values list in reverse
25        for i in range(n - 1, -1, -1):
26            # Pop the elements from the stack if they are smaller or equal
27            # to the current element since we are looking for the next larger element
28            while stack and stack[-1] <= valuesList[i]:
29                stack.pop()
30          
31            # If stack is not empty, assign the next larger element to answer
32            if stack:
33                answer[i] = stack[-1]
34          
35            # Push current value onto stack
36            stack.append(valuesList[i])
37      
38        # Return the filled answer list
39        return answer
40
1class Solution {
2
3    // Method to find the next larger node values for each node in the linked list
4    public int[] nextLargerNodes(ListNode head) {
5        // Use an ArrayList to store the values of the nodes for easier access
6        List<Integer> nodeValues = new ArrayList<>();
7        // Traverse the linked list and add values to the list
8        while (head != null) {
9            nodeValues.add(head.val);
10            head = head.next;
11        }
12
13        // Use a Deque as a stack to keep track of next larger element we have seen so far
14        Deque<Integer> stack = new ArrayDeque<>();
15        // Find the size of the linked list
16        int listSize = nodeValues.size();
17        // Create an array to store the result
18        int[] result = new int[listSize];
19      
20        // Traverse the list in reverse using the values ArrayList
21        for (int i = listSize - 1; i >= 0; --i) {
22            // Pop elements from the stack if they are less than or equal
23            // to the current node's value, since we are only interested
24            // in the next greater value
25            while (!stack.isEmpty() && stack.peek() <= nodeValues.get(i)) {
26                stack.pop();
27            }
28            // If the stack is not empty after popping, the current value at the top
29            // is the next greater value, so we add it to the result
30            if (!stack.isEmpty()) {
31                result[i] = stack.peek();
32            }
33            // Push the current node's value onto stack
34            stack.push(nodeValues.get(i));
35        }
36        // Return the populated result array containing next larger values
37        return result;
38    }
39}
40
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode(int x) : val(x), next(nullptr) {}
7 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
8 * };
9 */
10
11class Solution {
12public:
13    // Function to find the next greater node for each element in a linked list.
14    vector<int> nextLargerNodes(ListNode* head) {
15        vector<int> values; // This vector will hold the values of the nodes in the list
16
17        // Traverse the linked list and populate the values vector.
18        while (head != nullptr) {
19            values.push_back(head->val);
20            head = head->next;
21        }
22
23        // Initialize a stack to keep track of the next larger elements.
24        stack<int> stack;
25        // Determine the size of the values vector.
26        int size = values.size();
27        // Create a vector to store the answers (next larger elements).
28        vector<int> answers(size, 0); // Initialize with zeros.
29
30        // Loop through the values vector in reverse to find next larger elements.
31        for (int i = size - 1; i >= 0; --i) {
32            // Pop elements from the stack that are smaller or equal to the current element,
33            // since we want to find the next larger one.
34            while (!stack.empty() && stack.top() <= values[i]) {
35                stack.pop();
36            }
37            // If the stack is not empty, the top element is the next larger element.
38            if (!stack.empty()) {
39                answers[i] = stack.top();
40            }
41            // Push the current element onto the stack.
42            stack.push(values[i]);
43        }
44
45        // Return the vector with the next larger elements.
46        return answers;
47    }
48};
49
1/**
2 * Definition for singly-linked list.
3 */
4interface ListNode {
5    val: number;
6    next: ListNode | null;
7}
8
9/**
10 * Function to find the next larger value for every element of a linked list.
11 * @param head - The head of the linked list.
12 * @returns An array of next larger values.
13 */
14function nextLargerNodes(head: ListNode | null): number[] {
15    // Initialize an array to hold the list node values.
16    const valuesArray: number[] = [];
17  
18    // Traverse the linked list and populate the valuesArray with node values.
19    while (head !== null) {
20        valuesArray.push(head.val);
21        head = head.next;
22    }
23  
24    // Initialize a stack to keep track of the larger values.
25    const stack: number[] = [];
26    const length = valuesArray.length;
27    // Initialize an array to hold the answer.
28    const nextLargerValues: number[] = new Array(length).fill(0);
29  
30    // Iterate the valuesArray from the end to the beginning.
31    for (let i = length - 1; i >= 0; i--) {
32        // Pop elements from the stack that are less than or equal to the current value.
33        while (stack.length > 0 && stack[stack.length - 1] <= valuesArray[i]) {
34            stack.pop();
35        }
36      
37        // If stack is not empty, the top will be the next larger value.
38        nextLargerValues[i] = stack.length > 0 ? stack[stack.length - 1] : 0;
39      
40        // Push the current value onto the stack.
41        stack.push(valuesArray[i]);
42    }
43  
44    // Return the array of next larger values.
45    return nextLargerValues;
46}
47
Not Sure What to Study? Take the 2-min Quiz๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity

The time complexity of the given code involves iterating over all the elements of the linked list, followed by a single reverse iteration over the list of node values while maintaining a stack to keep track of the next larger node values. Specifically:

  • Converting the linked list to an array: We iterate over the linked list once, which has n elements, so this portion of the algorithm is O(n).

  • Next Larger Elements using a Stack: In the worst case, every element is pushed to and popped from the stack once. Because each element is handled twice (once for push and once for pop) in this process, and these are constant-time operations (assuming the stack's append and pop operations are O(1)), the complexity is O(2n), which simplifies to O(n).

Combined, since both operations are sequential and not nested, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

The space complexity of the algorithm arises from the space needed to store the list of values and the stack, in addition to the list used for the output:

  • Array of node values: The array to store node values has the same size as the number of nodes in the linked list, therefore the space complexity is O(n).

  • Stack: In the worst case, the stack might contain all n elements at the same time if the sequence is monotonically decreasing, which gives us a space complexity of O(n) for the stack.

  • Output list: An output list of size n is used to store the answer, resulting in a space complexity of O(n).

When we sum these up, we get O(n) + O(n) + O(n) which simplifies to O(n) overall space complexity as constants are dropped in big O notation.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ