@souravsain: Thanks man for a nice explaination
On Sun, Jun 27, 2010 at 12:02 AM, souravsain <[email protected]> wrote:
> @Raj
>
> You need to examine the nature of the array from end. If form end you
> move forward and you find elements are decreasing [10,12,14,16] then
> for each element, the previous is next higher. So keep pushing them on
> a stack. If you find an increase [say 11,10,12,14,16], then pop from
> stack till tap(stack) is greater than current element. This approach
> will be max 2n (invstigate that).
>
> Here is the algo
> NextHigher[last] = Nothing;//NextHIgher will have the solution and
> last = input array's size.
>
> while(--last>=1) //am asuming 1 based array and starting from last but
> one of array as last elment will always be Nothing.
> {
> if(array[las]<top(stack))
> {
> NextHigher[last]=top(stack);
> push(stack,array[last];
> }
> if(array[last]>=top(s))
> {
> while(array[last]>=top(stack) && !empty(stack)) //This loop
> will still keep time complexity 0(n) as there cannot be
> pop(stack); //more than n times of pop.
> if(empty(stack))
> NextHigher[last]=Nothing;
> else
> NextHigher[last]=top(stack);
> push(stack,array[last]);
>
> }
> }
>
> Thanks,
> Sourav Sain
>
> On Jun 25, 10:37 am, chitta koushik <[email protected]>
> wrote:
> > It works for the input given by you. Check the below code:
> >
> > import java.util.ArrayList;
> > import java.util.List;
> > import java.util.Stack;
> >
> > public class NextHigherElement {
> >
> > public static void main(String args[]){
> > List <Integer> input = new ArrayList<Integer>();
> > Stack<Integer> s = new Stack<Integer>();
> > input.add(4);
> > input.add(1);
> > input.add(3);
> > input.add(5);
> > input.add(6);
> > input.add(3);
> > input.add(2);
> > s.push(input.get(0));
> > for(int i=1;i<input.size();i++){
> > while( !s.isEmpty() && (input.get(i) > s.peek()) )
> > {
> > System.out.println(s.pop()+"**"+input.get(i));}
> >
> > s.push(input.get(i));}
> >
> > while(!s.isEmpty()){
> > System.out.println(s.pop()+"**"+"nothing");
> >
> > }
> > }
> > }
> >
> > --Koushik C
> >
> > On Thu, Jun 24, 2010 at 10:46 PM, Raj N <[email protected]> wrote:
> > > @Chitta: Hey this doesn't work in all cases. For eg: 4 1 3 5 6
> > > Output:
> > > 4-5
> > > 1-3
> > > 3-5
> > > 5-6
> > > 6-null
> >
> > > But according to ur logic u push 4 then, u push 1 as it is < 4, do u
> > > conclude that 4 doesn't have next higher element ?
> >
> > > On Thu, Jun 24, 2010 at 4:04 PM, chitta koushik <
> > > [email protected]> wrote:
> >
> > >> push the elements into stack , when the element to be pushed is
> greater
> > >> than the 'top' element.. pop the elements and write then
> >
> > >> eg : if array is 1 2 3 4 5 8 6
> >
> > >> insert 1
> > >> -----
> > >> stack : 1
> >
> > >> insert 2 ( as 2 > top i.e 1)
> > >> -----
> > >> output 1 - 2
> > >> stack : 2
> >
> > >> insert 3 ( as 3 > top i.e 2)
> > >> -----
> > >> output 1-2, 2-3
> > >> stack 3
> >
> > >> .
> > >> .
> > >> .
> > >> insert 8 ( as 8 > top i.e 5)
> > >> ------
> > >> output 1-2, 2-3,3-4,4-5
> > >> stack 8
> >
> > >> insert 6
> > >> -----------
> > >> output 1-2, 2-3,3-4,4-5,5-8
> > >> stack 8,6
> >
> > >> final output : 1-2, 2-3,3-4,4-5,5-8,8- -1 , 6 - -1
> >
> > >> On Wed, Jun 23, 2010 at 10:48 PM, Raj N <[email protected]> wrote:
> >
> > >>> @Kumar: The next higher of 5 will be 7 as it comes first in the
> array.
> >
> > >>> On Wed, Jun 23, 2010 at 5:28 PM, Kumar Vishal <[email protected]
> >wrote:
> >
> > >>>> hi the number should be just next higher element or any higher
> element
> >
> > >>>> like
> > >>>> if my arr is like
> >
> > >>>> arr= 2 5 1 3 7 6
> > >>>> the next higher element for 5
> > >>>> should be what (7 or 6 ) because 6 is more closer to 7 but 7 comes
> > >>>> first in arr
> >
> > >>>> On Wed, Jun 23, 2010 at 11:18 AM, Raj N <[email protected]> wrote:
> >
> > >>>>> Design a data structure to find the next higher element for each
> > >>>>> element in an array.
> > >>>>> For e.g. if array is 1 2 3 4 5 8 6
> > >>>>> o/p should be
> > >>>>> (element) (next higher element)
> > >>>>> 1 2
> > >>>>> 2 3
> > >>>>> 3 4
> > >>>>> 4 5
> > >>>>> 5 8
> > >>>>> 8 nothing
> > >>>>> 6 nothing
> >
> > >>>>> The array need not be sorted.
> > >>>>> Constraints-O(n) time complexity
> >
> > >>>>> --
> > >>>>> 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%[email protected]>
> <algogeeks%[email protected]<algogeeks%[email protected]>
> >
> > >>>>> .
> > >>>>> For more options, visit this group at
> > >>>>>http://groups.google.com/group/algogeeks?hl=en.
> >
> > >>>> --
> > >>>> Kumar Vishal
> > >>>> ____________________________
> > >>>> StAy HunGrY , StAy fOOlisH
> > >>>> ____________________________
> > >>>> Contact No:- 09560193839
> >
> > >>>> --
> > >>>> 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%[email protected]>
> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]>
> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]>
> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[email protected]>
> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[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.
