why sort? Can't we find the k largest elements and take their product if all are positive?

The Gateway to Computer Science Excellence

+4 votes

Best answer

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 kth largest element we repeat this process k times . So it takes klogn 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).

Therefore total time is O(n) + O(log n) = O(n).

+2

$k$ is also an input. Procedure is correct but can be optimized using the algorithm for finding kth largest element in $O(n)$.

0

@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..

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

@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

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,170 answers

193,841 comments

94,047 users