Next Greater Node In Linked List
Understanding the Problem
We have a singly linked list, and for each node we need to find the first node to its right that has a strictly larger value. If no such node exists, the answer is 0.
This is the classic "next greater element" problem applied to a linked list instead of an array. Linked lists don't support random access, so we copy the values into an array once and work from there. With the values in an array, the "next greater element" pattern is solved with a monotonic stack: process elements left to right and keep a stack of unresolved items still waiting for their answer.
Key Constraints:
1 <= n <= 10^4: With n up to 10,000, an O(n^2) brute force is feasible (about 100 million operations at worst), but we can do better with O(n).1 <= Node.val <= 10^9: Values are positive integers. No negatives or zeroes to worry about, so 0 as a sentinel for "no next greater" is safe.
Approach 1: Brute Force
Intuition
Convert the linked list to an array, then for each element scan to the right until a larger value appears. If the scan reaches the end without finding one, the answer is 0. This matches how you would solve it by hand: pick an element, look right, stop at the first value that is bigger.
Algorithm
- Traverse the linked list and store all node values in an array.
- Create a result array of the same size, initialized to 0.
- For each index
i, iterate through indicesjfromi + 1to the end. - If
values[j] > values[i], setresult[i] = values[j]and break out of the inner loop. - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Converting the linked list to an array takes O(n). Then for each of the n elements, we potentially scan up to n - 1 elements to the right, giving us O(n^2) comparisons in the worst case.
- Space Complexity: O(n). We store all node values in an array and create a result array, both of size n.
This approach repeats work. Each element scans right independently, learning nothing from previous scans. The next approach resolves several pending elements at once each time a larger value appears, which brings the total work down to O(n).
Approach 2: Monotonic Stack
Intuition
Instead of looking right from each element, we look left from each element. Scanning left to right, every new element answers the question for any earlier element it is larger than.
We maintain a stack of indices whose next greater element hasn't been found yet, kept in decreasing order of their values. When the current element is larger than the value at the stack's top index, it is the next greater value for that top element, so we pop the index and record the answer. We keep popping until the stack is empty or the top value is at least as large as the current value, then push the current index.
Each index is pushed once and popped at most once, so the total work is O(n).
At any point during the scan, the stack holds indices in decreasing order of their values. When the current value is larger than the top index's value, that current element is the first larger element to the right of the top: every index between them was either already popped (by an earlier value at least as large) or is still on the stack below the top with an even larger value, so none of them could be the answer for the top.
Each index enters the stack once and leaves at most once. Even with a while loop inside the for loop, the total number of push and pop operations is at most 2n, which is what makes the algorithm O(n).
Algorithm
- Traverse the linked list and store all node values in an array
values. - Create a result array of size n, initialized to 0.
- Create an empty stack that will store indices.
- Iterate through the array from left to right. For each index
i: - While the stack is not empty and
values[i] > values[stack.top()], pop the top index and setresult[popped_index] = values[i]. - Push
ionto the stack. - Any indices remaining in the stack have no next greater element (their result stays 0).
- Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Converting the linked list to an array takes O(n). The main loop runs n times, and each index is pushed and popped from the stack at most once, so total stack operations are O(n).
- Space Complexity: O(n). The values array, result array, and stack each use O(n) space in the worst case.