Re: [algogeeks] An Array Problem
What do you mean by " if this number is less than elements stored in stack " There have be N comparisons in the worst case. And that way, you have to do it for every element. So it will be governed by O(n^2) On Wed, Nov 23, 2011 at 12:50 AM, Aamir Khan wrote: > > > On Tue, Nov 22, 2011 at 11:50 PM, tech coder wrote: > >> here is an O(n) approach using a stack. >> >> problem can be stated as " find the 1st smaller element on the right. >> >> put the first element in stack. >> take next element suppose "num" if this number is less than elements >> stored in stack, pop those elements , for these pooped elements num will >> be the required number. >> put the the element (num) in stack. >> >> repeat this. >> >> at last the elements which are in next , they will have 0 (valaue) >> >> @techcoder : If the numbers are not in sorted order, What benefit the > stack would provide ? So, are you storing the numbers in sorted order > inside the stack ? > > I can think of this solution : > > Maintain a stack in which the elements will be stored in sorted order. Get > a new element from array and lets call this number as m. Push m into the > stack. Now, find all elements which are <= (m-1) using binary search. Pop > out all these elements and assign the value m in the output array. Elements > remaining at the end will have the value 0. > > I am not sure about the complexity of this algorithm... > > >> On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage wrote: >> >>> I can't think of a better than O(n^2) solution for this.. >>> Any one got anything better? >>> >>> >>> >>> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 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 -- 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. >>> >>> >>> -- >>> Anup Ghatage >>> >>> -- >>> 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. >>> >> >> >> >> -- >> * >> >> Regards* >> *"The Coder"* >> >> *"Life is a Game. The more u play, the more u win, the more u win , the >> more successfully u play"* >> >> -- >> 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. >> > > > > -- > Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee > > > -- > 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. > -- Anup Ghatage -- 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.
Re: [algogeeks] An Array Problem
On Tue, Nov 22, 2011 at 11:50 PM, tech coder wrote: > here is an O(n) approach using a stack. > > problem can be stated as " find the 1st smaller element on the right. > > put the first element in stack. > take next element suppose "num" if this number is less than elements > stored in stack, pop those elements , for these pooped elements num will > be the required number. > put the the element (num) in stack. > > repeat this. > > at last the elements which are in next , they will have 0 (valaue) > > @techcoder : If the numbers are not in sorted order, What benefit the stack would provide ? So, are you storing the numbers in sorted order inside the stack ? I can think of this solution : Maintain a stack in which the elements will be stored in sorted order. Get a new element from array and lets call this number as m. Push m into the stack. Now, find all elements which are <= (m-1) using binary search. Pop out all these elements and assign the value m in the output array. Elements remaining at the end will have the value 0. I am not sure about the complexity of this algorithm... > On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage wrote: > >> I can't think of a better than O(n^2) solution for this.. >> Any one got anything better? >> >> >> >> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 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 >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> Anup Ghatage >> >> -- >> 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. >> > > > > -- > * > > Regards* > *"The Coder"* > > *"Life is a Game. The more u play, the more u win, the more u win , the > more successfully u play"* > > -- > 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. > -- Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee -- 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.
Re: [algogeeks] An Array Problem
here is an O(n) approach using a stack. problem can be stated as " find the 1st smaller element on the right. put the first element in stack. take next element suppose "num" if this number is less than elements stored in stack, pop those elements , for these pooped elements num will be the required number. put the the element (num) in stack. repeat this. at last the elements which are in next , they will have 0 (valaue) On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage wrote: > I can't think of a better than O(n^2) solution for this.. > Any one got anything better? > > > > On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 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 >> >> -- >> 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. >> >> > > > -- > Anup Ghatage > > -- > 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. > -- * Regards* *"The Coder"* *"Life is a Game. The more u play, the more u win, the more u win , the more successfully u play"* -- 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.
Re: [algogeeks] An Array Problem
I can't think of a better than O(n^2) solution for this.. Any one got anything better? On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 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 > > -- > 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. > > -- Anup Ghatage -- 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.
[algogeeks] An Array Problem
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 -- 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.
