Problem of The Day: K-th Smallest Prime Fraction

Problem Statement

Intuition

I see the problem involves finding the kth smallest prime fraction from a given list of integers. Since we’re dealing with fractions and looking for the smallest ones, it might be helpful to consider sorting them somehow.

Approach

One approach could be to generate all possible fractions using the elements from the array. Then, we can use a min-heap to keep track of the smallest fractions. By popping elements from the heap k times, we can find the kth smallest fraction.

Complexity

• Time complexity: O(n^2 log k) where n is the the length of array. Generating all possible fractions takes O(n^2) time and each heap operation takes log k time

• Space complexity: O(n^2)

Code

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        min_heap = []
        N = len(arr)
        for i in range(N):
            for j in range(i + 1, N):
                val = arr[i] / arr[j]
                heapq.heappush(min_heap, [val, i, j])

        res = []
        for _ in range(k):
            res = heapq.heappop(min_heap)

        return [arr[res[1]], arr[res[2]]]

Max-heap Approach

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        max_heap = []
        N = len(arr)
        for i in range(N):
            for j in range(i + 1, N):
                val = arr[i] / arr[j]
                heapq.heappush(max_heap, [val * -1, i, j])
                if len(max_heap) > k:
                    heapq.heappop(max_heap)

        _, i, j = heapq.heappop(max_heap)
        return [arr[i], arr[j]]

Editorial Solution

Approach 2: Priority Queue

class Solution:
    def kthSmallestPrimeFraction(self, arr, k):
        # Create a priority queue to store pairs of fractions
        pq = []

        # Custom comparator for priority queue
        def compare(a, b):
            return a[0] - b[0]

        # Push the fractions formed by dividing each element by
        # the largest element into the priority queue
        for i in range(len(arr)):
            heapq.heappush(pq, ((arr[i] / arr[-1]), i, len(arr) - 1))

        # Iteratively remove the top element (smallest fraction)
        # and replace it with the next smallest fraction
        for _ in range(k - 1):
            cur = heapq.heappop(pq)
            numerator_index = cur[1]
            denominator_index = cur[2] - 1
            if denominator_index > numerator_index:
                heapq.heappush(pq, (
                    (arr[numerator_index] / arr[denominator_index]),
                    numerator_index,
                    denominator_index
                ))

        # Retrieve the kth smallest fraction from
        # the top of the priority queue
        result = heapq.heappop(pq)
        return [arr[result[1]], arr[result[2]]]