On Jan 30, 11:00 pm, ritu <[email protected]> wrote:
> You are given an array (unsorted) and for every element i, find the
> first occurance of an element j (in the remaining array) that is
> greater than or equal to i. If no such j occurs then print -1.
> Eg: Input---> A={1,3,5,7,6,4,8}
> Output---> 3 5 7 8 8 8 -1
> Time Complexity:O(n)
> Space Complexity:O(n)
I solved a version of this problem in my thesis.
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j >= i and B[j] > v.
Return -1 if no such j exists.
I have an application of this data structure in my thesis (which
is why I invented it) but I would love to hear other applications.
Ralph Boland
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
