CODEWITHSUNDEEP
arraysalgorithm
Lokesh
Lokesh

Reputation: 3112

kth largest element in all possible products of two arrays

Given two arrays A and B each of size N how to find the Kth largest element among the set X = {i x j | i ∈ A and j ∈ B}?

I came up with O(N^2 log(n)) solution by forming the set X, sorting it and then finding element at Kth position from last. Is there a better solution which has lower complexity?

Upvotes: 0

Views: 802

Answers (2)

Niklas B.
Niklas B.

Reputation: 95298

Given a candidate number, you can check in time O(N) using two pointers in the sorted representations of A and B what rank it has in the set {i x j | i ∈ A and j ∈ B}. Hence one possible solution is to use binary search on the value of i x j, with a runtime of O(N * (log N + log U)) where U is the size of the universe from which A and B are drawn.

Upvotes: 3

maxim1000
maxim1000

Reputation: 6365

There is a low-hanging fruit here - https://en.wikipedia.org/wiki/Quickselect (pay attention to the last section - it's possible to have worst case performance O(n) as well)

You just create array with all products and then select k-th element using the algorithm mentioned above. In total it will be O(n^2).

But I suspect there should be something better here...

Upvotes: 1

Related Questions