CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    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.

    Please help.

    Thanks

    Abhinav

  2. #2
    Join Date
    Sep 2013
    Posts
    13

    Re: Previous large element

    Quote Originally Posted by abhi1988srivastava View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured