LC786. K-th Smallest Fraction

Approach 1: Priority Queue / Heap

class Solution:
    def kthSmallestPrimeFraction(self, arr, k):
        pq = []
        n = len(arr)
 
        for i in range(n):
            heapq.heappush(
                pq,
                (arr[i] / arr[-1], i, n - 1)
            )
        
        for _ in range(k - 1):
            frac, inum, idenom = heapq.heappop(pq)
            
            idenom -= 1
 
            if inum < idenom:
                heapq.heappush(
                    pq,
                    (arr[inum] / arr[idenom], inum, idenom)
                )
        
        frac, inum, idenom = heapq.heappop(pq)
        return [arr[inum], arr[idenom]]
 

Complexity

Time: $O((n+k)\cdot log(n)$
Space: $O(n)$

Approach 2: Binary Search

TODO

Other Languages