Show problems as
Classic problem #503MediumArrayStackMonotonic Stack

Next Greater Element II

Real-world version: Loop Trail Next Rise
Tracked in this browser only
Read Next Greater Element II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey crew walked a closed loop trail and wrote down the signed elevation change at each marker, in walking order, as the array deltas. The trail closes on itself, so once you step past the final marker you are back at marker 0.

Stand at a marker and keep walking forward around the loop until you reach a marker whose elevation change is strictly larger than the one you started from. Report that larger change. If you make a full circuit without finding one, report -1 instead.

Return an array answer of the same length, where answer[i] is what you report from marker i. Elevation changes may themselves be negative, and -1 is a perfectly legal change, so a reported -1 carries no extra meaning: it may be a change of -1 that you walked to, or it may be the signal that the loop holds nothing larger.

Examples

Example 1

Input
deltas = [2, 7, 1]
Output
[7, -1, 2]

Marker 0 finds 7 one step ahead. Marker 1 holds the largest change on the loop, so it reports -1. Marker 2 has to wrap past the end to reach 2.

Example 2

Input
deltas = [-4, -9, -2]
Output
[-2, -2, -1]

Both of the first two markers walk forward to -2. Marker 2 already holds the largest change, so it reports -1.

Example 3

Input
deltas = [6, 6, 6]
Output
[-1, -1, -1]

An equal change is not a rise, so no marker ever finds one.

Constraints

  • 1 <= deltas.length <= 10^4
  • -10^9 <= deltas[i] <= 10^9

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.

Python
def next_rise(deltas: list[int]) -> list[int]:
Java
public int[] nextRise(int[] deltas)

More on the same topics