Find the Next Greater Value for Each Node in a Linked List
Solve this ProblemMedium20–25 min
Topics
Linked ListStackMonotonic Stack
Companies
AmazonGoogleBloombergFacebook
Given the
head of a singly linked list, return an array where each position holds the value of the first node further along the list that's strictly greater than the node at that position — or 0 if no such node exists.
Scanning rightward from every single node, one at a time, works but revisits the same ground over and over. A monotonic stackMonotonic StackA stack that's kept in strictly increasing or decreasing order at all times, by popping off anything that would break that order before pushing a new element. Perfect for "next greater/smaller" style questions: each element is pushed once and popped at most once, so the whole scan stays O(n) even though it looks like nested loops. answers every node's question in a single left-to-right pass — each node's value gets pushed once and popped at most once.
Test Case 1:
Input:head = [2, 1, 5]
Output:[5, 5, 0]
Explanation:Node 2's next greater value is 5 (skipping past 1); node 1's is 5; node 5 has none, so 0.
Test Case 2:
Input:head = [2, 7, 4, 3, 5]
Output:[7, 0, 5, 5, 0]
Explanation:Node 7 has nothing greater anywhere to its right, so its answer is 0.
Test Case 3:
Input:head = [9, 4, 4, 9, 9]
Output:[0, 9, 9, 0, 0]
Explanation:"Greater" means strictly greater — an equal value (4 followed by 4, or 9 followed by 9) doesn't count.
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
1 ≤ node value ≤ 10⁹
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int[] nextLargerNodes(Node head) { |
| 3 | List<Integer> vals = new ArrayList<>(); |
| 4 | Node curr = head; |
| 5 | while (curr != null) { |
| 6 | vals.add(curr.val); |
| 7 | curr = curr.next; |
| 8 | } |
| 9 | int n = vals.size(); |
| 10 | int[] result = new int[n]; |
| 11 | Deque<Integer> stack = new ArrayDeque<>(); |
| 12 | for (int i = 0; i < n; i++) { |
| 13 | while (!stack.isEmpty() && vals.get(stack.peek()) < vals.get(i)) { |
| 14 | result[stack.pop()] = vals.get(i); |
| 15 | } |
| 16 | stack.push(i); |
| 17 | } |
| 18 | return result; |
| 19 | } |
| 20 | } |
| 21 |
Array
Stack
empty
Array
0
0
0
0
1
2
Variables
curr
2INITIALIZE
vals will collect every node's value first (same as the brute force).
Step 1 / 18
Approach & Solutions
Brute Force — For Each Node, Scan Rightward
GoodCopy every node's value into an array. For each index i, scan forward from i + 1 until a strictly greater value turns up (that's the answer for i), or the array runs out (answer stays 0). Simple, but every node can trigger an O(n) scan of its own.
Time
O(n²)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public int[] nextLargerNodes(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 int n = vals.size();
16 int[] result = new int[n];
17 for (int i = 0; i < n; i++) {
18 int answer = 0;
19 for (int j = i + 1; j < n; j++) {
20 if (vals.get(j) > vals.get(i)) {
21 answer = vals.get(j);
22 break;
23 }
24 }
25 result[i] = answer;
26 }
27 return result;
28 }
29}Optimal — Monotonic Decreasing Stack of Indices
OptimalWalk the values left to right, keeping a stack of indices whose answer isn't known yet. Before pushing the current index, pop off every index on the stack whose value is smaller than the current one — the current value IS their answer. Because the stack only ever holds indices in decreasing order of value, each index is pushed once and popped at most once, giving a single O(n) pass.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public int[] nextLargerNodes(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 int n = vals.size();
16 int[] result = new int[n];
17 Deque<Integer> stack = new ArrayDeque<>();
18 for (int i = 0; i < n; i++) {
19 while (!stack.isEmpty() && vals.get(stack.peek()) < vals.get(i)) {
20 result[stack.pop()] = vals.get(i);
21 }
22 stack.push(i);
23 }
24 return result;
25 }
26}