@piyush: Just curious, how exactly can a stack be used in this
problem?
On Jul 26, 5:00 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Sorry for the above mistakeits not O(n)
On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Use stack
On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote:
Given an array of integers, for each element of the array, print the
first number on the right side of the element which is smaller than
it. print -1 is there is no such element.
eg: 3,4,2,18,19,1,10
Ans: 2,2,1,10,10,-1,-1
O(n^2) solution is trivial.
One solution could be:
Insert the elements of the array in a binary search tree. The moment a
node in the binary tree gets a left child, it is the element we are
looking for. All the nodes in the right subtree of a node which has
just received a left child can be assigned the value of the parents'
left child as the first smaller element to the right.
Thus, this solution is O(nlogn).
Does this solution work for all possible cases of input?
Is an O(n) solution possible?
--
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.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
* https://www.facebook.com/profile.php?id=10655377926 NEVER SAY
NEVER
*
--
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.
