1 votes 1 votes According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done in lesser time ? Algorithm Challenges algorithm-challenge placement-questions + – radha gogia asked Apr 10, 2016 retagged May 25, 2021 by Shiva Sagar Rao radha gogia 2.0k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Apr 10, 2016 reply Follow Share why sort? Can't we find the k largest elements and take their product if all are positive? 2 votes 2 votes radha gogia commented Apr 10, 2016 reply Follow Share ya so that can be done in O(n) time right ? 0 votes 0 votes Arjun commented Apr 10, 2016 reply Follow Share Yes, but we first have to find the kth largest element. 1 votes 1 votes srestha commented Apr 10, 2016 reply Follow Share say max element is X k element product is Xk So, time complexity is O(1) Am I wrong? 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes We build a max heap with the given $n$ elements. This will take $O(n)$ time to build the heap. Now every time we extract the root element and do heapify it takes $O(\log n)$ time. Since we have to extract $k^{th}$ largest element we repeat this process $k$ times. So it takes $k\log n$ time. $k$ being a constant here we can write it as $O(\log n)$ time. Therefore total time is $O(n) + O(\log n) = O(n)$. Riya Roy(Arayana) answered Apr 10, 2016 edited May 25, 2021 by Shiva Sagar Rao Riya Roy(Arayana) comment Share Follow See all 11 Comments See all 11 11 Comments reply Arjun commented Apr 10, 2016 reply Follow Share $k$ is also an input. Procedure is correct but can be optimized using the algorithm for finding kth largest element in $O(n)$. 2 votes 2 votes Riya Roy(Arayana) commented Apr 10, 2016 reply Follow Share Sir are you talking about quick sort ? 1 votes 1 votes Arjun commented Apr 10, 2016 reply Follow Share Default quick sort won't do this in linear time - but a variant of it can do. 2 votes 2 votes srestha commented Apr 11, 2016 reply Follow Share need quick sort because then no need to heapify again and again. right? 0 votes 0 votes rude commented May 30, 2016 reply Follow Share @arjun sir, I think she has given the perfect answer. If the K is also an input then also it will take only $k.log n$ time (maximum will be $n.log n$ time), which is definitely less than quicksort $k.n$ times (maximum will be $n^2$ times. . And actually this is a very famous interview problem, and she has stated the perfect solution. Which is suggested by some of the best profs. And you have suggested the Kth largest number algorithm, It perform real bad if K is very less. And its theoretically seems that perform better than heap method but its not a huge improvement. Its similar to strassen Matrix multiplication over general algorithm, covert 8 multiplication and 4 addition into 7 multiplication and 17 addition and shows some 0.19 improvement.. 0 votes 0 votes rude commented May 30, 2016 reply Follow Share @Arjun sir But here is the biggest question, Can you really modify the Kth order selection algorithm for this task.? I do not think so or it will not be that efficient then. 0 votes 0 votes Arjun commented May 30, 2016 reply Follow Share The complexity of given algorithm is $\max(n, k\lg n)$. So, we can modify the algorithm only when $k \lg n > n$ or $k > n/ \lg n$. Find the kth largest element in array - O(n) After this do a linear search on the array and multiply all elements >= kth largest. So, complexity remains $O(n)$. 0 votes 0 votes GateAspirant999 commented Mar 15, 2018 reply Follow Share Arjun sir not able to understand your procedure well. Also CLRS says we can prepare heap in O(nlogn) time with the note that asymptotically tight bound is O(n). Was just guessing if this statement can have any effect on the solution. 0 votes 0 votes srestha commented Mar 16, 2018 reply Follow Share quick select algorithm can sort and select all element in O(n) time So, it will take O(n) time Also by heapification it will take O(n) time 0 votes 0 votes akash.dinkar12 commented Mar 16, 2018 reply Follow Share @ srestha quick select algorithm??? 0 votes 0 votes srestha commented Mar 16, 2018 reply Follow Share hmm https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on 1 votes 1 votes Please log in or register to add a comment.