0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You're almost at an $O(n\log n)$ algorithm: there's more than linear search. You are looking for faster than naïve: I trust that you can use $o(1)$ additional storage. $\endgroup$ – greybeard Feb 14 at 5:43
  • $\begingroup$ @greybeard, ah right, I see how to get n*lgn. But I need linear. I can indeed use constant space. I though about maybe storing the max found so far, but couldn't think of a way to get linear from that. $\endgroup$ – Addem Feb 14 at 5:51
  • $\begingroup$ Sorry, I messed up. I intended $\omega(1)$, not omicron: significantly more than constant additional space. $\endgroup$ – greybeard Feb 14 at 5:58
  • 1
    $\begingroup$ Storing the max found so far is the right idea! In your example it would yield this: [1,2,2,2,2,6,6,6]. What do you need to do now? $\endgroup$ – Daniel Feb 14 at 9:42
  • $\begingroup$ @Daniel Sorry, not seeing it. $\endgroup$ – Addem Feb 15 at 16:21
1
$\begingroup$

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$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.