{x}
blog image

K-th Smallest Prime Fraction

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

 

Example 1:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

Input: arr = [1,7], k = 1
Output: [1,7]

 

Constraints:

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] is a prime number for i > 0.
  • All the numbers of arr are unique and sorted in strictly increasing order.
  • 1 <= k <= arr.length * (arr.length - 1) / 2

 

Follow up: Can you solve the problem with better than O(n2) complexity?

Solution Explanation:

This problem asks to find the k-th smallest fraction formed by pairs of numbers from a sorted array of prime numbers and 1. A naive approach would be to generate all possible fractions and sort them, but this has O(n^2) time complexity. A more efficient approach uses a min-heap to find the k-th smallest fraction in O(k log n) time.

Approach: Using a Min-Heap

  1. Initialization: We create a min-heap. Each element in the heap represents a fraction and stores:

    • The fraction's value (numerator / denominator). Note that we don't explicitly calculate the fraction's value, but rather store the numerator and denominator separately to prevent potential floating-point precision issues. The comparison logic in the heap will handle the fractional ordering.
    • The indices i and j of the numerator and denominator in the input array arr.

  2. Heap Population: Initially, the heap is populated with fractions where the numerator is arr[0] (which is always 1) and the denominators are all the other numbers in arr.

  3. Iterative Search: We repeatedly extract the minimum element (smallest fraction) from the heap k-1 times. After each extraction:

    • If there's a next possible fraction (i.e., we can increase the numerator index i without going out of bounds), we add the new fraction to the heap. This new fraction uses the next prime number as the numerator and maintains the same denominator.

  4. Result: After k-1 iterations, the top element of the heap is the k-th smallest fraction. We return the numerator and denominator of this fraction.

Time and Space Complexity

  • Time Complexity: Building the initial heap takes O(n log n) time in the worst case. Each extraction and insertion into the heap is O(log n). Since we perform this k-1 times, the overall time complexity is O(k log n). This is better than the O(n^2) complexity of a naive sorting approach, especially when k is relatively small compared to n.

  • Space Complexity: The heap can contain at most n elements at any point in time, so the space complexity is O(n).

Code Explanation (Python):

import heapq
 
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        h = [(arr[0] / y, 0, j + 1) for j, y in enumerate(arr[1:])] #Initial heap creation.  Note that we use tuple comparison
        heapq.heapify(h)                                          #for implicit fraction comparison
        for _ in range(k - 1):
            _, i, j = heapq.heappop(h)
            if i + 1 < j:
                heapq.heappush(h, (arr[i + 1] / arr[j], i + 1, j))
        return [arr[heapq.heappop(h)[1]], arr[heapq.heappop(h)[2]]] #Extract the final fraction

The other languages (Java, C++, Go) follow a similar approach, using their respective heap implementations (PriorityQueue in Java, priority_queue in C++, and container/heap in Go). The core logic of maintaining a min-heap and iteratively extracting the k-th smallest element remains the same across all implementations. The only significant difference is the syntax of heap operations and how custom comparator functions are used for fraction comparisons.