The next bigger number to the right

For every position, report the first number to its right that is larger than it. If there is no larger number to the right, report -1.

Worked example#

For [4, 5, 2, 25]:

So the answer is [5, 25, 25, -1].

The idea#

The obvious approach looks right from each position until it finds something larger. That is a nested loop, and on a hundred thousand numbers that are already sorted downwards it does five billion comparisons.

The way out is to notice what the slow version keeps re-reading. Walk left to right and hold a stack of positions still waiting for an answer. When a new value arrives, it is the answer for every waiting position smaller than it, so pop those and fill them in. Then the new position waits its own turn.

Every position is pushed once and popped at most once, so the whole thing is one pass no matter how the numbers are arranged.

Notice the shape the stack holds: reading bottom to top, the values never increase. A stack kept in order like that is called monotonic, and once you see it here you will see it in stock spans, in histograms and in rainwater.

Constraints#

• 1 <= n <= 100000
• -1000000000 <= nums[i] <= 1000000000