Next Larger on a Ring
MediumStack
Problem
Seats around a round table hold numbers nums; after the last seat comes the first one again. For each seat, walk clockwise (increasing index, wrapping around) and find the first number strictly larger than the one on that seat.
Return an array with that number for every seat, or -1 if no seat on the whole ring holds a larger number.
Example 1
- Input:
- nums = [3, 8, 4, 1]
- Output:
- [8, -1, 8, 3]
From 4 we pass 1, wrap to 3, then reach 8. From 1 we wrap straight to 3.
Example 2
- Input:
- nums = [5, 5, 5]
- Output:
- [-1, -1, -1]
Constraints
- 1 ≤ nums.length ≤ 10^4
- -10^9 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
Without the wrap-around this is the classic next-greater problem with a monotonic stack. How do you simulate the wrap?
Walkthrough
How to approach it
01Clarify before coding
- Strictly larger? Yes, equal values do not count.
- Does the search stop after one full lap? Yes; if nothing larger exists anywhere, the answer is -1.
- Are duplicates allowed? Yes, and they must still get correct answers.
02Brute force
For each seat, step through the next n - 1 seats with modular indexing until a larger number appears.
Cost: O(n²): 10^8 steps for n = 10^4 in the worst case.
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.