Next Greater Element I
Real-world version: Auction Watchlist HighsThe statement here is our own: the same inputs, outputs and technique.
An auction house sold its lots one after another and recorded the hammer price of each lot in sales, in the order the lots went under the hammer. No two lots fetched the same price.
A dealer kept a watchlist of prices, each of which is one of the recorded prices. For every price on the watchlist, the dealer wants to know the price of the first lot sold after that lot which fetched a strictly higher price. When no later lot beat it, the answer for that price is -1.
Return the answers in the same order as watchlist.
Examples
Example 1
- Input
- watchlist = [9, 3], sales = [3, 9, 5, 12]
- Output
- [12, 9]
The lot that fetched 9 was followed by 5, which is lower, then by 12, which beats it. The lot that fetched 3 was beaten right away by 9.
Example 2
- Input
- watchlist = [2, 10, 5], sales = [10, 2, 5, 7]
- Output
- [5, -1, 7]
After the lot at 2 came 5, which is higher. Nothing after the opening lot at 10 beat it, so its answer is -1. After 5 came 7.
Example 3
- Input
- watchlist = [6], sales = [9, 6, 1]
- Output
- [-1]
The lot at 9 sold before the watched lot, so it does not count; the only later lot fetched 1.
Constraints
- 1 <= watchlist.length <= sales.length <= 1000
- 0 <= watchlist[i], sales[i] <= 10^4
- All prices within watchlist are distinct, and all prices within sales are distinct
- Every price in watchlist appears in sales
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def next_higher_sale(watchlist: list[int], sales: list[int]) -> list[int]:public int[] nextHigherSale(int[] watchlist, int[] sales)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 9 test cases: 9 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's
More on the same topics
- Final Prices With a Special Discount in a ShopReal-world version: Job Hour CreditsEasy
- Daily TemperaturesReal-world version: Nights Until a Fuller HouseMedium
- Next Greater Element IIReal-world version: Loop Trail Next RiseMedium
- Sum of Subarray MinimumsReal-world version: Weakest Reading Per StretchMedium