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 ith node (1-indexed). If the ith 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:
n.1 <= n <= 1041 <= Node.val <= 109In #1019 Next Greater Node In Linked List, the goal is to find the next node with a greater value for each node in a singly linked list. Since linked lists do not support random access, a helpful strategy is to first traverse the list and store node values in an array. This makes it easier to process elements by index.
The optimal technique uses a monotonic decreasing stack. As you iterate through the array, maintain a stack that stores indices of elements whose next greater value has not yet been found. When the current value is greater than the value at the index on top of the stack, you can resolve that index by setting its next greater value. This process continues until the stack condition is restored.
This approach ensures each element is pushed and popped at most once, giving an efficient O(n) time complexity with O(n) extra space for the stack and result array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Array Conversion + Monotonic Stack | O(n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
We can use a stack that stores nodes in monotone decreasing order of value. When we see a node_j with a larger value, every node_i in the stack has next_larger(node_i) = node_j .
This approach leverages a monotonic stack to efficiently find the next greater element for each node in the linked list. By traversing the linked list once, we can maintain a stack to track potentially greater nodes and update results as we traverse.
Time Complexity: O(n), where n is the length of the linked list, because each node is pushed and popped from the stack at most once.
Space Complexity: O(n), needed for storing the result and stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for singly-linked list.
5struct ListNode {
6 int val;
7
This C solution uses an array-based stack to capture and process nodes from the linked list. As each node is encountered, it checks the stack for any nodes smaller than the current node. If found, it updates the result set. The code is efficient and operates in O(n) time complexity.
In this approach, reverse the linked list initially and then traverse, keeping track of the next greatest node using a stack. As this traversal is reversed, use a stack to efficiently find and keep the nearest greatest value.
Time Complexity: O(n)
Space Complexity: O(n)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Converting the linked list to an array simplifies indexing and traversal. Since stacks typically work with indices for efficient updates, using an array allows you to track positions and update the result array easily while applying the monotonic stack technique.
Yes, variations of next greater element problems frequently appear in FAANG and other top tech interviews. This question tests understanding of stacks, monotonic data structures, and efficient linear-time processing of sequences.
A monotonic stack is the most effective data structure for this problem. It helps maintain elements in decreasing order and quickly identifies when a greater value appears. This pattern is commonly used in 'next greater element' problems.
The optimal approach converts the linked list into an array and then applies a monotonic decreasing stack to track indices whose next greater value has not yet been found. As you iterate through the array, you resolve elements when a larger value appears. This ensures each element is processed at most twice, making the solution efficient.
In this approach, the linked list is reversed first. As we traverse from the new start, greater elements are stacked and compared for finding the next greater node. At the end, a final reversal of results provides the answer.