Suppose you have an array `nums`

of integers, unsorted, containing the values from 1 to n. You have a second array, call it `firstBigger`

, initially empty, which you want to populate with integers such that `firstBigger[i]`

contains j if j is the least index such that i < j and `nums[j] > nums[i]`

. A brute force search of `nums`

runs in n^2 time. I need to find a linear time search.

For example, if `nums = [4,6,3,2,1,7,5]`

and we use 1-indexing, then `firstBiggest = [2,6,6,6,6,None,None]`

.

I have considered first computing the array of differences in linear time. Certainly anywhere in the array of differences with a positive value, this indicates a place in `firstBigger`

where it should store i+1. But I’m not seeing how to fill any other coordinates efficiently.

I might have gotten close when I started thinking of analyzing the array end-to-start. The last nth coordinate of `firstBigger`

is going to be None, the n-1th has to be directly compared to the nth. As we proceed backward, if the number at i is smaller than at i+1 we make this assignment. Otherwise we look up the first number bigger than the one at i+1. If that’s still too small, again look up the first number bigger than that.

On average this does better than the naive algorithm, but in the worst case it’s still n^2. I can’t see any room to optimize this.