Hi,
This can be solved the technique to use stacks to save incomplete problems.
Push first element to stack.
While iterating over the array,
if the element is smaller than stack top, push it to stack along with index.
if the element is larger than stack top, pop till current element
is smaller than stack top and for all the popped indices store the
current element.
time complexity: o(n)
space complexity: o(n)
The same technique is used to solved largest rectangle in a histogram
and largest rectangle with all 1s in a binary matrix.
Thanks,
Balaji.
On Mon, Jan 31, 2011 at 1:25 PM, ritu <[email protected]> wrote:
> for {9,7,8} it gives me {8,8,-1}...not correct
>
> On Jan 31, 11:16 am, abhijith reddy <[email protected]> wrote:
>> simple dp
>>
>> void solve(int *arr,int sz)
>> {
>> int ans[sz];
>> ans[sz-1]=-1;
>> for(int i=sz-2;i>=0;i--)
>> {
>> if(arr[i]<arr[i+1]) ans[i]=arr[i+1];
>> else ans[i]=ans[i+1];
>> }
>> for(int i=0;i<sz;i++)
>> printf("%d ",ans[i]);
>>
>>
>>
>> }
>> On Sun, Jan 30, 2011 at 10: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)
>>
>> > --
>> > 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]<algogeeks%2Bunsubscribe@googlegroups.com>
>> > .
>> > For more options, visit this group at
>> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>>
>> - Show quoted text -
>
> --
> 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.
>
>
--
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.
