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)
1import heapq
2
3class Solution:
4 def kthSmallestPrimeFraction(self, arr, k):
5 n = len(arr)
6 pq = [(arr[i] / arr[j], i, j) for i in range(n) for j in range(i + 1, n)]
7 heapq.heapify(pq)
8 while k > 1:
9 heapq.heappop(pq)
10 k -= 1
11 return pq[0][1], pq[0][2]Python uses a min-heap for k operations. All fractions are calculated and stored in the priority queue. We pop the smallest fraction k times to achieve the desired k-th smallest fraction.
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)
1With 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.