@Balaji.....nice solution..but care to explain how it is applied in the
other 2 problems you mentioned at the end(Rectangle in a histogram and
largest rectangle in the binary matrix ..)
On Mon, Jan 31, 2011 at 2:21 PM, Balaji Ramani <rbalaji.psgt...@gmail.com>wrote:
> 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 <ritugarg.c...@gmail.com> wrote:
> > for {9,7,8} it gives me {8,8,-1}...not correct
> >
> > On Jan 31, 11:16 am, abhijith reddy <abhijith200...@gmail.com> 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 <ritugarg.c...@gmail.com> 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 algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
