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 $O(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
firstBigger = [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 $n$th coordinate of
firstBigger is going to be None, the $n-1$th has to be directly compared to the $n$th. 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.