K-th Smallest Prime Fraction — Binary Search on Fraction Value [LC 786, Google]

Problem Statement#

Given a sorted array arr of distinct primes (plus 1 at index 0), return the k-th smallest fraction formed by arr[i] / arr[j] where i < j.

Constraints:

• 2 <= arr.length <= 1000
• 1 <= arr[0] < arr[1] < ... < arr[arr.length - 1] <= 3 * 10^4
• arr[0] == 1
• arr contains prime numbers, except for arr[0]
• 1 <= k <= arr.length * (arr.length - 1) / 2

Input:  arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: Fractions: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. Sorted: 1/5 < 1/3 < 2/5 < 1/2 < 3/5 < 2/3. The 3rd smallest is 2/5.

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

Why This Problem Matters#

LC 786 is a hard problem asked by Google and Facebook that combines binary search on a continuous value space with a two-pointer counting technique. It is a direct extension of the pattern used in LC 378 (Kth Smallest in Sorted Matrix) but applied to implicit fractions rather than matrix entries.

The problem is notable because the search space is continuous (real-valued fractions), not discrete. Binary search on a floating-point range with an epsilon termination condition is a powerful technique for problems where the answer is a real value.

The Core Insight#

Binary search on fraction value m in [0.0, 1.0]. For each candidate m, count the number of fractions arr[i] / arr[j] <= m using two pointers: for each i, find the smallest j where arr[i] / arr[j] <= m (equivalently, arr[i] <= m * arr[j]). Since arr is sorted, as i increases, the valid j threshold can only decrease or stay, so j is monotone.

Also track the largest fraction seen that is <= m — this is the exact kth fraction when the count equals k.

If count == k, return the tracked fraction. If count > k, the answer is smaller (hi = mid). If count < k, the answer is larger (lo = mid).

Visual Dry Run#

arr = [1,2,3,5], all fractions: 1/5=0.2, 1/3=0.333, 2/5=0.4, 1/2=0.5, 3/5=0.6, 2/3=0.667

Binary search with mid = 0.5:

• i=0 (arr[0]=1): j advances until arr[j] >= 1/0.5 = 2. j=1 (arr[1]=2). Fractions <= 0.5: arr[0]/arr[1], arr[0]/arr[2], arr[0]/arr[3] = 3 fractions. Max = 1/2.
• i=1 (arr[1]=2): j advances until arr[j] >= 2/0.5 = 4. j=3 (arr[3]=5). Fractions: arr[1]/arr[3] = 1 fraction. Max = max(1/2, 2/5) = 1/2.
• i=2: arr[2]=3 >= arr[3]=5*0.5=2.5, so 3/5>0.5. No fractions.
• count = 4 > k=3, so hi = 0.5.

Continue until count == 3 and we find [2,5].

Solution (Optimal)#

class Solution:
    def kthSmallestPrimeFraction(self, arr: list[int], k: int) -> list[int]:
        n = len(arr)
        lo, hi = 0.0, 1.0
 
        while hi - lo > 1e-9:
            mid = (lo + hi) / 2
            count = 0
            max_frac = 0.0
            p, q = 0, 1
            j = 1
 
            for i in range(n - 1):
                # Find smallest j where arr[i]/arr[j] <= mid, i.e., arr[i] <= mid*arr[j]
                while j < n and arr[i] > mid * arr[j]:
                    j += 1
                count += n - j  # all arr[j], arr[j+1], ..., arr[n-1] give valid fractions
 
                if j < n and arr[i] / arr[j] > max_frac:
                    max_frac = arr[i] / arr[j]
                    p, q = arr[i], arr[j]
 
            if count == k:
                return [p, q]
            elif count > k:
                hi = mid
            else:
                lo = mid
 
        return []

var kthSmallestPrimeFraction = function(arr, k) {
    const n = arr.length;
    let lo = 0.0, hi = 1.0;
 
    while (hi - lo > 1e-9) {
        const mid = (lo + hi) / 2;
        let count = 0;
        let maxFrac = 0.0;
        let p = 0, q = 1;
        let j = 1;
 
        for (let i = 0; i < n - 1; i++) {
            while (j < n && arr[i] > mid * arr[j]) j++;
            count += n - j;
 
            if (j < n && arr[i] / arr[j] > maxFrac) {
                maxFrac = arr[i] / arr[j];
                p = arr[i];
                q = arr[j];
            }
        }
 
        if (count === k) return [p, q];
        else if (count > k) hi = mid;
        else lo = mid;
    }
 
    return [];
};

Time: O(n log(1/epsilon)) — about 50 iterations for 1e-9 epsilon, each O(n) two-pointer pass Space: O(1) — only pointer and tracking variables

Common Mistakes#

• Using an integer binary search instead of floating-point — fractions are real-valued, not integers.
• Resetting j to 1 for each i — since j is monotone as i increases, it must carry over between loop iterations (not reset).
• Comparing arr[i] / arr[j] > mid directly — precision issues in floating-point; use arr[i] > mid * arr[j] for integer comparisons.
• Returning when count == k without tracking the exact fraction — you need to track the largest valid fraction seen during the two-pointer scan.
• Not handling the epsilon termination correctly — the loop should terminate when hi - lo < 1e-9 (or similar small threshold).

Interview Tips#

• Explain the two-pointer technique for counting before writing any code: "for each i, j can only stay or increase as i increases."
• Mention why floating-point binary search is needed: "the answer is a fraction, not an integer, so the search space is continuous."
• State the epsilon: "I'll terminate when hi - lo < 1e-9 since we only need the numerator and denominator, which are integers."
• The heap-based alternative (O(k log n)) is valid but slower for large k — mention it as a comparison.

Follow-up Questions#

• Heap approach: Push all (arr[0]/arr[j], 0, j) tuples for all valid j. Pop k times, pushing the next fraction with the same denominator. O(k log n).
• LC 378 (Kth Smallest in Sorted Matrix): Same binary search on value with two-pointer counting per row.
• What if arr is not sorted? Sort first — the two-pointer counting requires sorted order.
• Floating-point precision: The answer [p, q] is exact (integers) because count == k fires at the exact boundary.

Key Takeaways#

• LC 786 uses binary search on a continuous floating-point range [0.0, 1.0], not on discrete indices or values.
• The counting function uses two monotone pointers: as i increases (larger numerator), j can only stay or increase (valid denominator threshold rises), giving O(n) per count pass.
• Track the largest valid fraction during counting — this is the exact answer when count == k.
• Terminate when hi - lo < 1e-9 (epsilon loop) rather than on exact integer equality.
• The comparison arr[i] > mid * arr[j] avoids floating-point division for the boundary check inside the two-pointer loop.
• Google and Facebook ask this to verify that candidates can apply binary search to continuous domains and combine it with two-pointer counting.
• The heap alternative (O(k log n)) works for small k but is slower for large k; binary search is O(n log(1/eps)) regardless of k.