Re: [algogeeks] Give Algo to do this in O(n)
@Shiva: How can min heap be uesd, can you eloborate a bit. As far as i see, the best possible is O(nlogn) i.e by sorting and scanning over the complete array once. On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo shiv.jays...@gmail.com wrote: I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg ankurga...@gmail.com wrote: Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of 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. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ThanksRegards: -sandeep -- 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] Give Algo to do this in O(n)
just find minimum and secon minimum by taking two variables in O(n) On 10 October 2011 17:57, sandeep nagamalli nsandee...@gmail.com wrote: @Shiva: How can min heap be uesd, can you eloborate a bit. As far as i see, the best possible is O(nlogn) i.e by sorting and scanning over the complete array once. On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo shiv.jays...@gmail.comwrote: I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg ankurga...@gmail.comwrote: Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of 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. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ThanksRegards: -sandeep -- 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. -- **With Regards Deoki Nandan Vishwakarma IIT ROORKEE 9760340784 for Computer Science Interview Material see my home page https://sites.google.com/site/deokinandanmaterials/ * * -- 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] Give Algo to do this in O(n)
@ ankur: if space is not the consideration first sort them using count sort and then look for the pair with the min. difference .. i think it should work . Snehi On Mon, Oct 10, 2011 at 7:21 PM, anubhav gupta anubhav.7...@gmail.comwrote: @deoki try for 1001,999,998,1 On Mon, Oct 10, 2011 at 6:57 PM, Deoki Nandan deok...@gmail.com wrote: just find minimum and secon minimum by taking two variables in O(n) On 10 October 2011 17:57, sandeep nagamalli nsandee...@gmail.com wrote: @Shiva: How can min heap be uesd, can you eloborate a bit. As far as i see, the best possible is O(nlogn) i.e by sorting and scanning over the complete array once. On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo shiv.jays...@gmail.comwrote: I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg ankurga...@gmail.comwrote: Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of 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. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ThanksRegards: -sandeep -- 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. -- **With Regards Deoki Nandan Vishwakarma IIT ROORKEE 9760340784 for Computer Science Interview Material see my home page https://sites.google.com/site/deokinandanmaterials/ * * -- 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. -- 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. -- 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] Give Algo to do this in O(n)
Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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] Give Algo to do this in O(n)
@Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 sravanreddy...@gmail.comwrote: Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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. -- 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] Give Algo to do this in O(n)
ankur : i wont say its the best way, but it can be used in one traversal the range can be determined and then count sort can be applied. On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg ankurga...@gmail.com wrote: @Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 sravanreddy...@gmail.com wrote: Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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. -- 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. -- 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] Give Algo to do this in O(n)
Counting Sort is really a Bad option for this Problem as range is not given yes range can be find in single traversal but think if largest element is 10^9 and size of the array is just about 10^3 Counting Sort = O(10^9) Simple Sorting = O(10^4) Counting sort will perform bad in this case both in terms of Space Requirements and Time On Mon, Oct 10, 2011 at 11:25 PM, snehi jain snehijai...@gmail.com wrote: ankur : i wont say its the best way, but it can be used in one traversal the range can be determined and then count sort can be applied. On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg ankurga...@gmail.com wrote: @Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 sravanreddy...@gmail.com wrote: Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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. -- 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. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,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.
[algogeeks] Give Algo to do this in O(n)
Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Give Algo to do this in O(n)
I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg ankurga...@gmail.com wrote: Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of 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. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
