tag:blogger.com,1999:blog-3418265334198879901.post1281286927212748700..comments2023-06-10T14:12:41.433+05:30Comments on Coders Stop: Find the second largest number in an arrayAviralhttp://www.blogger.com/profile/11920144614598355124noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3418265334198879901.post-78609627720678396302011-02-03T20:28:06.736+05:302011-02-03T20:28:06.736+05:30you don't need to construct the tree itself(wh...you don't need to construct the tree itself(which would cost you nlogn in creation itself). The formation of tree is via the recursion (something like merge sort and D&C). <br />You can read more on<br />http://en.wikipedia.org/wiki/Selection_algorithm#Tournament_Algorithm<br /><br />RegardsAviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-58534575902109025442011-02-03T19:05:23.221+05:302011-02-03T19:05:23.221+05:30but,the tree approach requires another auxillary s...but,the tree approach requires another auxillary space O(n)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-25918216768772925252011-02-01T23:09:20.962+05:302011-02-01T23:09:20.962+05:30@abhijeet ... ur solution takes a total of 2*n-3 c...@abhijeet ... ur solution takes a total of 2*n-3 comparisons.. while the method suggested by abhishek(tournament principle) takes the only (n-1)+logn steps which is surely more optimised than yours.<br /><br />RegardsAviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-13908606992160252132011-02-01T22:59:14.484+05:302011-02-01T22:59:14.484+05:30guys you have to solve this O(n) and there is solu...guys you have to solve this O(n) and there is solution to this problem...<br /><br />take two variable and save the largest in variable and second largest in the second one.. scan through the array... and finally you have second largest element... :).. it's that simple and it is the Adobe written question on dec. 2010...<br /><br />happy coding.<br />abhijeetAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-14780906911928296002011-01-23T01:44:08.663+05:302011-01-23T01:44:08.663+05:30yeah binary tree approach is better as in quick so...yeah binary tree approach is better as in quick sort modification ur worst case boils down to O(n^2).... you can have a look for finding other similar algorithms in selection algorithm<br />http://en.wikipedia.org/wiki/Selection_algorithmAviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-9340153571104679712011-01-23T01:31:31.407+05:302011-01-23T01:31:31.407+05:30Split the array in two parts as in quick sort usin...Split the array in two parts as in quick sort using pivot element where left contains smaller and right contains larger element.<br />Recursively split the right part till it contains only 1 elements.<br />Now pivot is the 2nd largest number in the array<br /><br />Is it better then binary tree approach ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-73372970752510391192011-01-23T01:02:03.337+05:302011-01-23T01:02:03.337+05:30@aviral sir
thanxs sir@aviral sir <br /> thanxs sirAbhishek Prajapatinoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-81696290343242640452011-01-23T00:48:56.944+05:302011-01-23T00:48:56.944+05:30@abhishek .. nice one... more commonly this approa...@abhishek .. nice one... more commonly this approach is known as tournament algorithm<br />RegardsAviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-19074465374506111722011-01-23T00:29:51.039+05:302011-01-23T00:29:51.039+05:30@aviral sir
i have considered binary t...@aviral sir<br /> i have considered binary tree approach we have do exactly n-1 comparisons to find the max element now the max. element at each level of the binary tree wins the comparison so there would have been (log n)levels <br />in the tree so the second max. element fall among these elements now to compute the 2 nd max. we can compute the max. element of the array which consists these log(n) elements which can be done in log(n)-1 ways ............Abhishek Prajapatinoreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-49552200826745018172011-01-23T00:13:20.429+05:302011-01-23T00:13:20.429+05:30@abhishek ... yeah but i think it should be (n-1)+...@abhishek ... yeah but i think it should be (n-1)+log(n) ..can u share ur approach or method also....Aviralhttps://www.blogger.com/profile/11920144614598355124noreply@blogger.comtag:blogger.com,1999:blog-3418265334198879901.post-66668773088249235932011-01-22T21:25:02.770+05:302011-01-22T21:25:02.770+05:30Sir
Minimum number of comparisons will be (n-1...Sir <br /> Minimum number of comparisons will be (n-1) +(log n -1)<br />n-1 for maximum element and (log n ) -1 is for second maximum element.<br />Abhishek Prajapati<br />NIT jsrAnonymousnoreply@blogger.com