
September 7th, 2013, 09:24 AM
#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{j0 ≤ j < i; aj > ai};
in which assume a0 = ∞
O(n) should be the running time.
Please help.
Thanks
Abhinav

September 24th, 2013, 05:15 AM
#2
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 topofstack it's a hit. You've found the first bigger element to the left of the topofstack element. The stack is popped. If the element is bigger than the new topofstack 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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
