Creating a patterned array in linear time

Question

Given an integer array P[1..n], we want to build an array S[1..n]:

Among the members in P[1..i-1] that are larger than P[i], we choose P[k] with the largest index (1<=k< i <=n). S[i] will hold the value of P[k]. If there are no numbers greater than P[i] in P[1..i-1] we place 0 in S[i].

Obviously, the first element in S[] will be 0, as there are no elements before it. The others can be found using iteration through the array P[], however, that will take O(n^2), as it is the sum of the series 1+2+...+n=[1/2n(n+1)].

Is there a way to do this in linear time? I have thought about using stacks, as it will help with pulling the highest index with a larger value, however, any way I try to implement it still requires me to go through the created stack, so it is actually worse - time to create the stack, and time to pop out until reaching the desired element, all over again and again. Perhaps there's another way?

Any ideas/suggestions/hints on how it could be done?

Examples:

P[5,4,9,7,8]-->S[0,5,0,9,9]
P[1,5,2,3]-->S[0,0,5,5]

Clarification:

We should assign to S[i] the highest indexed number, still greater than P[i] in P[1..i-1]. For example, assume P[8,2,1]. While 8 is the greatest value, S[3] will hold the value 2, as it is the highest indexed number still greater than P[3]. -->S[0,8,2].

Edit:

I believe I have an O(n) solution, using a stack. the idea in pseudocode:

BuildS(P[])
    Temp-StackNIL
    for(i<--1 up to n)
        while(Temp-Stack≠NIL)
            if(P[i]<=top[Temp-Stack])
                pop(Temp-Stack) //goes back to while
            else
                S[i]<--top[Temp-Stack]
                push(Temp-Stack,P[i]) //goes back to for
        S[i]<--0 //out of while
        push(Temp-Stack,P[i]) //goes back to for

Am I having it right?

Answer 1

I do not think there is an O(n) solution, although I came up with O(n log n).

Suppose we have a binary search tree (BST). Main loop pseudocode:

for i in [0, len(P)):
    S[i] = BST.search(P[i])    
    BST.insert(P[i], i)

I assume that search returns S[i] for P[i].

def search(value):

    def getSbyIndex(index):
        return index == -inf ? 0 : P[index]

    curVertex = BST.root
    maxIndex = -inf
    while:
        if curVertex.value > value:
            if !(curVertex.leftChild exists):
                return getSbyIndex(maxIndex)
            else:
                maxIndex = max(maxIndex, curVertex.index, curVertex.rightChild.subtreeMaxIndex)
                if curVertex.leftChild.value <= value:
                    return getSbyIndex(maxIndex)
                else:
                    curVertex = curVertex.leftChild
        else:
            if !(curVertex.rightChild exists):
                return getSbyIndex(maxIndex)
            else:
                curVertex = curVertex.rightChild

I wrote search unoptimized (and also did not check some nonexistent vertices cases for the sake of simplicity, be careful!) on purpose to give you the general idea. We start from the root of BST and go down by usual rules updating maxIndex when it is needed (see explanation below). Each leaf of our BST (which actually represents some P[x]) contains 5 fields:

• leftChild
• rightChild
• value (that P[x])
• index (x)
• subtreeMaxIndex (maximum of .index among vertices of a subtree with the current vertex as a root)

So when is it needed? Let's say we have curVertex.value <= value. It means we have to go to the right subtree. Any vertex.value of the left subtree is also <= value, so there are no vertices (P[y]) in the left subtree and in the current vertex that fulfill the P[y] > P[new] condition, therefore we do not change maxIndex.

Similarly, let's pretend we have curVertex.value > value, which leads us to the left subtree. But this time any vertex.value of the right subtree is vertex.value > value, so all P[y] among the current and the right subtree vertices are actually greater than P[new], so we have to find their maximal index, which equals to max(curVertex.index, curVertex.rightChild.subtreeMaxIndex), and try to update maxIndex with it.

The last thing we need is insert.

def insert(value, index):
    newVertex = BST.insertNode(value)
    newVertex.index = index
    curVertex = newVertex
    while curVertex is not BST.root:
        curVertex.subtreeMaxIndex = max(curVertex.index, curVertex.leftChild.subtreeMaxIndex, curVertex.rightChild.subtreeMaxIndex)
        curVertex = curVertex.parent

Here I did not check for children existence again, and also added parent field. BST.insertNode is just a basic BST inserting method, which returns us a new vertex object. After that we just go upwards to the root, updating .subtreeMaxIndex for every vertex on the path.

Overall, we have n iterations of the main loop and log n for both insert and search calls, so the final complexity is O(n log n).

Answer 2

There is actually a solution in O(n)

The idea is to keep track of the highest value encountered while looping through P and compare P[i] to this value.

Here is the pseudocode I came up with (using your first example)

P = [1,5,2,3]
S = []
highest = 0

for i in P
    if highest < P[i]
        highest = P[i]
        S[i] = 0
    else
        S[i] = highest

I assumed here that you used only values >= 0 but if you got negative values highest should be initialized with the minimum value possible.