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)
1
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)
1class Solution:
2 def kthSmallestPrimeFraction(self, arr, k):
3 low, high = 0.0, 1.0
4 n = len(arr)
5 while high - low > 1e-9:
6 mid = (low + high) / 2
7 p = q = -1
8 max_fraction = 0.0
9 total = i = 0
10 for j in range(1, n):
11 while i < j and arr[i] < arr[j] * mid:
12 i += 1
13 total += i
14 if i > 0:
15 fraction = arr[i - 1] / arr[j]
16 if fraction > max_fraction:
17 max_fraction = fraction
18 p, q = arr[i - 1], arr[j]
19 if total < k:
20 low = mid
21 else:
22 high = mid
23 result = [p, q]
24 return resultWith Python, binary search narrows the range of potential fraction values. Using two-pointers enables a count of fractions less than a midpoint, helping binary search converge on the k-th smallest.