1
$\begingroup$

I'm required to perform the following operation on an array in O(n): P[1..n] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the beginning of the array until I reach an element whose value is greater than P[i], or reach the beginning of the array. The output of the function should be an array S[1..n] that contains these values.

For example, if:

 P = [ 4, 3, 6, 1, 2, 7, 9 ]

Then I must create this array:

 S = [ 1, 1, 3, 1, 2, 6, 7 ]

If I start at P[3] (=6), I can advance 3 cells until the beginning of the array, and therefore S[3] = 3; but if I start at P[5] (=2) I will advance only 2 cells and reach P[3] (=6 > 2), so S[5] = 2.

Implementing such algorithm in O(n^2) is trivial, but I'm required to do so in O(n). I was hinted to use a stack.

$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Dec 27 '14 at 21:47
  • $\begingroup$ Well, I wrote the naive solution in O(n^2) and tried to see where I can "cut" some of the comparisons by using a stack, but I didn't really have any idea where and how to use a stack in this case, nor what should the values in the stack represent. I did come up with a few optimizations, for example, storing the maximum value of every sub array of P starting with P[1] in another array Q, which would cut some of the calculations of S's cells to O(1), but this will still make the algorithm O(n^2). $\endgroup$ – LIJI Dec 27 '14 at 21:55
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 14 '17 at 19:50
  • $\begingroup$ Sounds related to left-right maxima. $\endgroup$ – Raphael Jan 14 '17 at 19:50
1
$\begingroup$

Yes, you can perform this operation in $O(n)$ using a stack $\mathbb{S}$.

Before presenting the algorithm directly, I would like to give you an illustration using your example. It is not difficult for you to discover the basic idea on your own.

For your example, I give the states of the stack $\mathbb{S}$. Element $P[i]$ and its $S[i]$ are denoted by a pair (P[i], S[i]). The stack reads from left (bottom) to right (top).

Notice which elements are popped before (when) $P[i]$ is pushed and how (and why) $S[i]$ is computed (described as // comments).

initialization: empty
P[0] = 4: (4,1)
P[1] = 3: (4,1), (3,1)  
P[2] = 6: (6,3)    // 3 = 1 + 1 + 1
P[3] = 1: (6,3), (1,1)
P[4] = 2: (6,3), (2,2)  // 2 = 1 + 1
P[5] = 7: (7,6)   // 6 = 2 + 3 + 1  
P[6] = 9: (9,7)   // 7 = 6 + 1

Here is the basic idea.

Stack $\mathbb{S}$ stores the elements $P[i]$ in array $P$ and its corresponding (already computed) $S[i]$.

Initialization: $\mathbb{S}=\emptyset; \quad \forall i: S[i]=0.$

For each element $P[i]$ in array $P$ in order:

  1. $\textsf{Pop}$ the elements in stack $\mathbb{S}$, until it encounters a bigger one than $P[i]$. This step simulates the "advance toward" procedure. Meanwhile, compute the sum of the $s$ values of all elements that are popped by $P[i]$. Then, $S[i]$ for $P[i]$ equals $1$ plus this sum.

  2. Then $\textsf{Push}$ $P[i]$ and its corresponding value $S[i]$ (just computed) into $\mathbb{S}$.

$\endgroup$
  • $\begingroup$ It seems so obvious now that I can see it, thanks! $\endgroup$ – LIJI Dec 29 '14 at 23:53
1
$\begingroup$

The following algorithm is $O(n)$ and uses a stack, the stack have the elements that have not found an answer to the problem, the idea is to iterate the array backwards and in each iteration while the i-th element is greater than the popped element from the stack then the i-th element is the closest greater element (to the left) to the element that was popped.

These are the steps:

First initialize the $P$ array with these values:

  • $P[0]$ = 1 , thats it because it can't go further to the left.
  • $P[1]$ = 1, no matter what if the first element is greater than the second one it is a move, if not it stills moving until reach to the beggining so in any case is always 1.
  • $P[i] = i +1$, $\forall_{1<i<n} $

That initialization is the "worst possible case" where there is no element greater to the left, in other words when a strictly increasing array is given as an input.

The algorithm:

  1. Initialize the stack with the last element of the array.
  2. Iterate backwards from the size-2 position, lets call the i-th element $current$.
  3. While $current$ is greater than the popped element do the following: lets call the popped element "prev", $P[prev.index] = prev.index - i$. Here we are saying that $current$ is the closest element to the left greater than $prev$, so we put the number of steps is has to be moved, namely $prev.index - i$.
  4. Now, if $prev$ is greater than $current$ it means that there has not been an answer to $prev$ so far, so we push it to the stack again.
  5. After each iteration push $current$ to the stack, so its answer can be computed further in the algorithm.

Correctness

The loop invariant is that in the stack there is always the element for whom the algorithm hasn't found answer yet, so we keep pushing and if we found a element that is greater than the popped element we assign the answer as shown. In this sense we can say that this is a Greedy Algorithm, because it relies on as soon as we found a element greater than the popped element we put the answer "locally" without comparing further (Which of course would make it $O(n^2)$), is guaranteed that it is the correct answer because as we are going backwards the first time we see a element that is greater than the elements in the stack is going to correspond to number of times that the element has to be moved. If after the main loop of the algorithm is done there still elements in the stack it means that those elements are greater than all the elements to their left, and since we initialized $P$ with the "worst possible case", then the algorithm is correct.

Running time

For each element there is only 4 possible operations: The first insertion into the stack, pop the element in order to check if $current$ is greater than $prev$, put the element back if $prev$ > $current$, and finally pop the element when the answer is found. That would give us $4n$ in the worst case and indeed that is $O(n)$.

Last but not least, some python code

def f(A):
stack = [ (A[len(A)-1],len(A)-1) ]

ans = [-1]*len(A)
ans[0] = 1
ans[1] = 1
i = 2
while i < len(ans):
    ans[i] = i + 1
    i = i + 1

i = len(A)-2
while i >=0:
    current = A[i]
    if len(stack) > 0:
        prev = stack.pop()
        while current > prev[0]:
            ans[prev[1]] = prev[1]-i
            if len(stack) > 0:
                prev = stack.pop()
            else:
                break

        if prev[0] > current:
            stack.append(prev)

    stack.append( (current, i) )
    i = i - 1




return ans
$\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.