@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 <koushik.infin...@gmail.com>
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 <rajn...@gmail.com> 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 <
> > koushik.infin...@gmail.com> 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 <rajn...@gmail.com> 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 <kumar...@gmail.com>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 <rajn...@gmail.com> 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 algoge...@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.
>
> >>>> --
> >>>> 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 algoge...@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 algoge...@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 algoge...@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 algoge...@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 algoge...@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.
