A linear time algorithm to find the array of indices of bigger numbers

Question

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.

Answer 1

Let $A$ be an array with indizes $1$ to $n$. We first build the array $B$ where $B[i] = j$ indicates that index $j$ has the highest value $A[j]$ in the first $i$ entries of $A$. Then we build a list $L$ which has the numbers from $B$ in the same order but without duplicates in it. Then we define the function $f$ as $f(i) = L[i+1]$ or none if $L[i+1]$ does not exist. The final result is applying $f$ to $B$.

Let's look again at your example $A = [4,6,2,3,1,7,5]$. Then $B = [1,2,2,2,2,6,6]$ and $L = [1,2,6]$. Hence the function $f$ is $1 \mapsto 2, 2 \mapsto 6, 6\mapsto \textrm{none}$. Applying $f$ to $B$ gives us $[2,6,6,6,6,\textrm{none},\textrm{none}]$.

Computing $B$ and $L$ runs clearly in linear time (for $L$ we only need to append values to a list at its end). Applying $f$ takes linear time too, if done correctly: Either you have an look up table as array of length $n$ (or hash map if you're ok with expected worst-case analysis). Or you use the monotonicity of $B$ and use the list $L$ which you traverse in lock-step when traversing $B$. This approach has the benefit that it uses less space in some instances and cache efficiency may be better since the relevant information is stored next to each other in consecutive order (worst case is still $n$).