Previous large element
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Sep 2013
Posts
1

## 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.

Thanks

Abhinav

2. Junior Member
Join Date
Sep 2013
Posts
13

## Re: Previous large element

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.
Last edited by dazzle; September 24th, 2013 at 10:13 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•