Next Greater Node In Linked List

Medium
2015.

Next Greater Node In Linked List

Next Greater Node In Linked List is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Microsoft interviews.

You are given the head of a singly linked list with n nodes. For each node, find the value of the first node after it whose value is strictly larger.

Return an integer array answer where answer[i] is that value for the i-th node (0-indexed), or 0 if no later node is larger.

Example 1

Input
head = [2,1,5]
Output
[5,5,0]
Explanation
Both 2 and 1 first meet 5; nothing after 5 is larger.

Example 2

Input
head = [2,7,4,3,5]
Output
[7,0,5,5,0]

Example 3

Input
head = [4,4,4]
Output
[0,0,0]
Explanation
An equal value is not larger.

Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 10^4
  • 1 <= Node.val <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nextLargerNodes = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Next Greater Node In Linked List — Problem & Solution

Next Greater Node In Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Next Greater Node In Linked List is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Stack, Monotonic Stack
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the head of a singly linked list with n nodes. For each node, find the value of the first node after it whose value is strictly larger.

Return an integer array answer where answer[i] is that value for the i-th node (0-indexed), or 0 if no later node is larger.

Example 1

Input: head = [2,1,5]
Output: [5,5,0]
Explanation: Both 2 and 1 first meet 5; nothing after 5 is larger.

Example 2

Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3

Input: head = [4,4,4]
Output: [0,0,0]
Explanation: An equal value is not larger.

Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 10^4
  • 1 <= Node.val <= 10^9

Hints for Next Greater Node In Linked List

  1. Hint 1

    Checking every later node for every node is O(n²) — too slow for 10^4 nodes in the worst case.

  2. Hint 2

    Copy the values into an array so positions can be addressed, and keep a stack of positions that are still waiting for a larger value.

  3. Hint 3

    Keep the waiting values decreasing: when a new value arrives, it is the answer for every waiting position with a smaller value — pop them and record it. Then push the new position.

How to solve Next Greater Node In Linked List

A monotonic stack: the positions still waiting for a larger value always have non-increasing values from bottom to top, so a new value resolves a run of them from the top in one go.

Approach

  1. Read the list into an array vals; let answer be n zeros.
  2. For each index i: while the stack is non-empty and vals[top] < vals[i], pop top and set answer[top] = vals[i].
  3. Push i.
  4. Positions left on the stack never meet a larger value and keep their 0; return answer.

Why it works

When vals[i] pops index j, every index between them was either popped earlier by a value ≤ vals[i]'s competitors or is still above j — in both cases no value between them exceeded vals[j] before i, otherwise j would already have been popped. So vals[i] is the first larger value after j. Each index is pushed and popped at most once.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Use strict < when popping: an equal value does not count as larger.
  • Store indices, not values, on the stack — the answer is written by position.
  • Values reach 10^9, which still fits in a 32-bit int; no arithmetic is done on them.

Reference solution

Python

from typing import List, Optional

def nextLargerNodes(head: Optional[ListNode]) -> List[int]:
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    answer = [0] * len(vals)
    stack = []
    for i, v in enumerate(vals):
        while stack and vals[stack[-1]] < v:
            answer[stack.pop()] = v
        stack.append(i)
    return answer

Java

public static int[] nextLargerNodes(ListNode head) {
    java.util.ArrayList<Integer> vals = new java.util.ArrayList<>();
    for (; head != null; head = head.next) vals.add(head.val);
    int n = vals.size();
    int[] answer = new int[n];
    int[] stack = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        int v = vals.get(i);
        while (top > 0 && vals.get(stack[top - 1]) < v) answer[stack[--top]] = v;
        stack[top++] = i;
    }
    return answer;
}

C++

vector<int> nextLargerNodes(ListNode* head) {
    vector<int> vals;
    for (; head; head = head->next) vals.push_back(head->val);
    vector<int> answer(vals.size(), 0), stack;
    for (int i = 0; i < (int) vals.size(); i++) {
        while (!stack.empty() && vals[stack.back()] < vals[i]) { answer[stack.back()] = vals[i]; stack.pop_back(); }
        stack.push_back(i);
    }
    return answer;
}

JavaScript

var nextLargerNodes = function(head) {
    var vals = [];
    for (; head !== null; head = head.next) vals.push(head.val);
    var answer = new Array(vals.length).fill(0), stack = [];
    for (var i = 0; i < vals.length; i++) {
        while (stack.length > 0 && vals[stack[stack.length - 1]] < vals[i]) answer[stack.pop()] = vals[i];
        stack.push(i);
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure