got a O(n) soln guys
Starts from an empty stack and scan the input array (IN) from the bottom (i
= n-1):
for(int i = n-1; i >= 0; i--) {
while (!stack.isEmpty() && IN[i] <= stack.top()) {
stack.pop();
}
if (stack.isEmpty()) {
OUT[i] = 0;
stack.add(IN[i]);
continue;
}
if (IN[i] > stack.top()) {
OUT[i] = stack.top();
stack.push(IN[i];
continue;
}
}
On Sun, Feb 6, 2011 at 10:59 PM, jalaj jaiswal <[email protected]>wrote:
> Input: A unsorted array of size n.
> Output: An array of size n.
> Relationship:
> > elements of input array and output array have 1:1 correspondence.
> > output[i] is equal to the input[j] (j>i) which is smaller than input[i]
> and jth is nearest to ith ( i.e. first element which is smaller).
> > If no such element exists for Input[i] then output[i]=0.
> Eg.
> Input: 1 5 7 6 3 16 29 2 7
> Output: 0 3 6 3 2 2 2 0 0
>
> --
> With Regards,
> *Jalaj Jaiswal* (+919019947895)
> Final Year Undergraduate,
> IIIT ALLAHABAD
>
>
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Final Year Undergraduate,
IIIT ALLAHABAD
--
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.
