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.1k 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 Show 8 previous comments 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.