Next Greater Value Lookup
Problem
You are given a list nums of distinct integers and a list queries whose values all appear somewhere in nums. For each query value, find the first value to its right in nums that is larger than it, or -1 when no larger value follows. Return the answers in query order.
Examples
Input: nums = [4, 1, 3, 6, 2, 5], queries = [1, 3, 2, 6]
Output: [3, 6, 5, -1]
Why: 1 is followed by 3, 3 by 6 and 2 by 5, while nothing after 6 is largerInput: nums = [5, 4, 3, 2, 1], queries = [4, 1]
Output: [-1, -1]
Why: the list only falls, so no value ever has a larger one after itInput: nums = [7], queries = [7]
Output: [-1]
Why: edge case, a single value has nothing to its rightHints
0 / 3
Scanning right from every query position works, but it is quadratic when many values wait a long time for something larger. Can one pass over nums answer every value at once?
Keep the values that are still waiting for a larger one. When a new value arrives, every waiting value smaller than it has just found its answer. The waiting values always form a falling run, so the smaller ones sit on top.
Walk nums with a stack. While the top of the stack is smaller than the current value, pop it and record the current value as its answer in a dictionary. Push the current value. Finally, look each query up in the dictionary, defaulting to -1.
Solution
A value waits on the stack until the first larger value arrives, and at that moment it is on top, because anything pushed after it and still waiting is smaller than it. So one left-to-right pass pops each value exactly when its answer shows up and records the pair in a dictionary, and whatever is still on the stack at the end never got an answer. The queries are then plain lookups. Every value is pushed and popped at most once, so time is O(n + q) and space is O(n).
def next_greater_lookup(nums, queries):
answer = {}
stack = [] # waiting values, falling from bottom to top
for x in nums:
while stack and stack[-1] < x:
answer[stack.pop()] = x # x is the first larger value after it
stack.append(x)
return [answer.get(q, -1) for q in queries]
print(next_greater_lookup([4, 1, 3, 6, 2, 5], [1, 3, 2, 6])) # -> [3, 6, 5, -1]
print(next_greater_lookup([5, 4, 3, 2, 1], [4, 1])) # -> [-1, -1]
print(next_greater_lookup([7], [7])) # -> [-1]Stuck on the idea rather than the code? Monotonic Stack covers it.