Find the next greatest element in a linked list.

The most efficient way to find the next greater element for each node in a linked list is by using a monotonic decreasing stack. This approach processes the list, typically from right to left, to identify the first element to the right that is strictly greater than the current element.

Mechanics and Why it Works

A monotonic stack maintains elements in a specific order (either strictly increasing or decreasing). For this problem, a decreasing stack is used. As we iterate through the linked list elements in reverse order (right-to-left), we compare the current element with the stack's top. If the stack's top is less than or equal to the current element, it cannot be the "next greater" for any subsequent elements to its left, so we pop it. This continues until the stack is empty or its top is greater than the current element. If the stack is not empty, its top is the next greater element for the current node. Finally, the current element is pushed onto the stack. This ensures that the stack always contains potential "next greater" candidates in decreasing order.

The time complexity is O(N) because each element is pushed and popped from the stack at most once. The space complexity is O(N) in the worst case (e.g., a strictly decreasing list) for storing the stack.

Implementation and Applications

Since linked lists don't allow direct right-to-left traversal, a common approach is to first convert the linked list into an array or list of values. This takes O(N) time and space. Then, apply the monotonic stack algorithm to this temporary array.

def next_greater_elements(nums):
    stack = []
    results = [-1] * len(nums)
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack:
            results[i] = stack[-1]
        stack.append(nums[i])
    return results

This pattern is fundamental for problems like finding the next larger partition in a data processing pipeline, where you might need to identify the next data block (e.g., in Snowflake micro-partitions or Spark partitions) that satisfies a certain condition.

In the interview, also mention…

Discuss variations like finding the "next smaller element" or handling circular arrays (often solved by doubling the array or iterating twice). Also, mention applications such as the "stock span problem" or calculating areas in histograms.