Sponsored
Sponsored
This approach uses a min-heap to efficiently find the kth smallest fraction. By iterating through each pair of elements (i, j) in the array where i < j, we can calculate the fraction arr[i]/arr[j] and push it into the heap. The heap is then used to retrieve the k-th smallest element efficiently.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
1var kthSmallestPrimeFraction = function(arr, k) {
2 let n = arr.length;
3 let heap = new MinPriorityQueue({
4 compare: (a, b) => arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]
5 });
6
7 for(let i = 0; i < n; i++) {
8 heap.enqueue([i, n - 1]);
9 }
10 let res = null;
11 while(k--) {
12 res = heap.dequeue().element;
13 if(res[1] - 1 > res[0]) heap.enqueue([res[0], res[1] - 1]);
14 }
15 return [arr[res[0]], arr[res[1]]];
16};This JavaScript implementation leverages a MinPriorityQueue for extracting the k-th smallest fraction. The queue uses a custom comparator function to compare based on calculated fraction values.
This approach uses binary search on the value of fractions. By implementing a search over the potential range of fraction values, the algorithm counts how many fractions are less than a given mid-point, narrowing down to the k-th one by manipulating the bounds of the potential fraction values. A two-pointer technique helps count the fractions efficiently.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
1
Utilizing JavaScript, binary search reduces the possible range for fraction values. A two-pointer setup helps count smaller fractions, determining bounds for pinpointing the k-th smallest fraction.