K-th Smallest Prime Fraction

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:
Input: A = [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, 2/3.
The third fraction is 2/5.

Input: A = [1, 7], K = 1
Output: [1, 7]

Note:

• A will have length between 2 and 2000.

• Each A[i] will be between 1 and 30000.

• K will be between 1 and A.length * (A.length - 1) / 2.

class Solution {
    // Similar to
    // https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        int n = A.length;
        // Min heap
        // Adding smallest fraction with each digit at numerator
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> A[a[0]] * A[b[1]] - A[b[0]] * A[a[1]]);
        for (int i = 0; i < n - 1; i++)
            pq.add(new int[] { i, n - 1 });

        while (K > 1) {
            int[] top = pq.poll();
            top[1]--;
            if (top[1] > top[0])
                pq.add(top);
            K--;
        }
        return new int[] { A[pq.peek()[0]], A[pq.peek()[1]] };
    }
}
// Binary Search
public class Solution {
    private int[] countPairs(int[] A, double x) {
        // p,q hold the biggest fraction <= x
        int count = 0, n = A.length, p = 0, q = 0;
        double max = 0.0;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < i && (double) A[j] / (double) A[i] < x)
                j++;
            if (j > 0) {
                double fraction = (double) A[j - 1] / (double) A[i];
                if (max < fraction) {
                    max = fraction;
                    p = A[j - 1];
                    q = A[i];
                }
            }
            count += j;
        }
        return new int[] { count, p, q };
    }

    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        int n = A.length, min = A[0], max = A[n - 1], p = 0, q = 0;
        double lo = (double) min / (double) max, hi = 1.0;
        while (lo < hi) {
            double mid = (lo + hi) / 2.0;
            // Count number of fractions <= mid
            int[] count = countPairs(A, mid);
            if (count[0] == K) {
                p = count[1];
                q = count[2];
                break;
            }
            if (count[0] < K)
                lo = mid;
            else
                hi = mid;
        }
        return new int[] { p, q };
    }
}