Solution: Kth Smallest Prime Fraction

Explore how to find the kth smallest fraction formed from a sorted array of unique prime numbers and 1. Learn to implement a heap-based k-way merge algorithm that iteratively processes fractions by numerator and denominator indices to extract the desired fraction efficiently. Understand the approach's time and space complexities and how it manages data using a min heap.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given a sorted array of unique integers, arr, which includes the number $1$ and other prime numbers. You are also given an integer $k$ .

For every index $i$ and $j$ where $0 \leq i < j <$ arr.length, you can form a fraction by taking the number at index $i$ as the numerator and the number at index $j$ as the denominator, resulting in the fraction arr[i] / arr[j].

Your task is to return the $k^{th}$ smallest fraction among these fractions. The answer should be returned as an array of two integers, where the first element, answer[0], is the numerator (arr[i]), and the second element, answer[1], is the denominator (arr[j]) corresponding to the $k^{th}$ smallest fraction.

Constraints:

$2 \leq$ arr.length $\leq 10^3$
...