Next Larger From a Reference List
EasyStack
Problem
A reference list ref holds distinct integers. A list of queries holds some of those same integers (each at most once).
For each query value q, find where q sits in ref and return the first value to its right in ref that is larger than q, or -1 if there is none. Answer in the order of queries.
Example 1
- Input:
- queries = [3, 1, 6], ref = [1, 3, 5, 2, 6, 4]
- Output:
- [5, 3, -1]
After 3 comes 5; after 1 comes 3; nothing after 6 is larger.
Example 2
- Input:
- queries = [4], ref = [4, 1, 2]
- Output:
- [-1]
Constraints
- 1 ≤ queries.length ≤ ref.length ≤ 10^5
- All values in ref are distinct; every query appears in ref
- -10^9 ≤ values ≤ 10^9
Hint
Show the first hint
Answer the question for every value of ref first; then answering queries is a lookup.
Walkthrough
How to approach it
01Clarify before coding
- Are values distinct? Yes, so value → position is unambiguous.
- Strictly larger? Yes.
- Must answers follow query order? Yes.
02Brute force
For each query, find its position in ref and scan right for the first larger value.
Cost: O(q · n): up to 10^10 operations at the limits.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.