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

<p>For every <code>i</code> and <code>j</code> where <code>0 &lt;= i &lt; j &lt; arr.length</code>, we consider the fraction <code>arr[i] / arr[j]</code>.</p>

<p>Return <em>the</em> <code>k<sup>th</sup></code> <em>smallest fraction considered</em>. Return your answer as an array of integers of size <code>2</code>, where <code>answer[0] == arr[i]</code> and <code>answer[1] == arr[j]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,5], k = 3
<strong>Output:</strong> [2,5]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,7], k = 1
<strong>Output:</strong> [1,7]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>arr[0] == 1</code></li>
	<li><code>arr[i]</code> is a <strong>prime</strong> number for <code>i &gt; 0</code>.</li>
	<li>All the numbers of <code>arr</code> are <strong>unique</strong> and sorted in <strong>strictly increasing</strong> order.</li>
	<li><code>1 &lt;= k &lt;= arr.length * (arr.length - 1) / 2</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Can you solve the problem with better than <code>O(n<sup>2</sup>)</code> complexity?
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        """
        Suppose our array is: [n_0, n_1, n_2, n_3, n_4], so that n_0 = 1.
        Then if we arrange the possible fractions like:

        n_0/n_4  n_0/n_3  n_0/n_2  n_0/n_1

        n_1/n_4  n_1/n_3  n_1/n_2

        n_2/n_4  n_2/n_3

        n_3/n_4

        Then notice the top-left is the smallest. Then the next smallest is either n_0/n_3
        or n_1/n_4. So we can use a min-heap to keep track of the smallest for us. So put both
        of these numbers in the min-heap.

        If we pop, then suppose we get n_0/n_3. Then the next smallest is either whatever we have
        in the heap already (so n_1/n_4), or it can be the fraction on the right of n_0/n_3: n_0/n_2,
        or the fraction under n_0/n_3: n_1/n_3. So we add these two to the heap.

        The pattern continues: whenever we pop an element from the heap, we add the fraction to the
        right and the fraction under the element.

        If we heappop k times, then that's the element we want. But we also have to keep track
        that we don't re-add the same element, so we also have a set() that keeps track of what
        we have seen.
        """
        import heapq
        N = len(arr)

        hh = [(arr[0] / arr[N - 1], 0, N - 1)]
        count = 0
        seen = set()
        while count < k:
            frac_val, numer_idx, denom_idx = heapq.heappop(hh)
            count += 1
            
            if numer_idx < N - 1:
                new_frac = arr[numer_idx + 1] / arr[denom_idx]
                if new_frac not in seen:
                    heapq.heappush(
                        hh,
                        (arr[numer_idx + 1] / arr[denom_idx], numer_idx + 1, denom_idx)
                    )
                    seen.add(new_frac)
            
            if denom_idx > 0:
                new_frac = arr[numer_idx] / arr[denom_idx - 1]
                if new_frac not in seen:
                    heapq.heappush(
                        hh,
                        (arr[numer_idx] / arr[denom_idx - 1], numer_idx, denom_idx - 1)
                    )
                    seen.add(new_frac)
            
            
        return [arr[numer_idx], arr[denom_idx]]


27537