Previous large element

Hi everyone,

Given a sequence of n numbers, {a1; a2; · · · ; an}, for each element
ai
, 1 ≤ i ≤ n, nd the index of the rightmost element inside {a1; a2; · · · ; ai1} whose value is
strictly larger than ai
. If no element is larger than ai then output 0. In other words,  for
each i
pi = max{j|0 ≤ j < i; aj > ai};
in which assume a0 = ∞

O(n) should be the running time.

Please help.

Thanks

Abhinav

Quote:

---

Originally Posted by abhi1988srivastava

O(n) should be the running time.

---

So for each element in an array you want to find the closest bigger element to the left?

I think this can be accomplished in O(N) with the use of a stack.

You scan the array in reverse (from right to left) and consider each array element in turn. If an element is bigger than the top-of-stack it's a hit. You've found the first bigger element to the left of the top-of-stack element. The stack is popped. If the element is bigger than the new top-of-stack too it's another hit so the stack is popped again, etcetera. Then the element is pushed and the next array element in turn is considered.

Each of the N array elements is pushed and popped once at the most. Since push/pop are O(1) operations the total complexity will be O(N).

Key to this low complexity is that a stack can be used rather than a tree (which would've resulted in O(N * logN)). And this is possible because the structure of the algorithm keeps the stack in sorted order automagically, avoiding explicit ordering.