K-th Smallest Prime Fraction — Solution

Problem

Given a sorted array of distinct integers containing 1 and prime numbers, and an integer k, find the k-th smallest fraction formed by pairing any element arr[i] as the numerator with any element arr[j] as the denominator, where i is strictly less than j. Return the result as [numerator, denominator].

For arr = [1, 2, 3, 5] and k = 3, the six valid fractions sorted smallest to largest are: 1/5 < 1/3 < 2/5 < 1/2 < 3/5 < 2/3.

• Input: arr = [1, 2, 3, 5], k = 3
• Output: [2, 5]
• Explanation: The third smallest fraction is 2/5, so we return its numerator and denominator.

Counter-example: for k = 1, the answer would be [1, 5] (the smallest fraction 1/5), not [1, 2].

Intuition

This generates n×(n-1)/2 fractions from a sorted array. The key observation is that fixing the denominator arr[j] produces a sorted sequence of fractions: arr[0]/arr[j] < arr[1]/arr[j] < ... < arr[j-1]/arr[j]. The problem becomes: merge n sorted sequences and find the k-th element overall — a classic min-heap application. Alternatively, since all fractions lie in (0, 1), binary search on the fraction value lets us count how many fractions fall below a midpoint in linear time, converging to the exact answer.

Approach 1 — Brute Force

Generate every valid fraction, sort them all, and return the k-th entry. Simple to implement but builds and sorts the entire list even though we only need one element.

1. For every pair (i, j) with i < j, record arr[i], arr[j], and their ratio.
2. Sort all fractions by value.
3. Return the numerator and denominator at position k−1 (0-indexed).

1def kthSmallestPrimeFraction(arr: list[int], k: int) -> list[int]:
2    fractions = []
3    n = len(arr)
4    for i in range(n):
5        for j in range(i + 1, n):
6            fractions.append((arr[i] / arr[j], arr[i], arr[j]))
7    fractions.sort()
8    _, numerator, denominator = fractions[k - 1]
9    return [numerator, denominator]

Time: O(n² log n) — generating n(n-1)/2 fractions and sorting them.
Space: O(n²) — storing every fraction simultaneously.

Approach 2 — Min-Heap

Model each denominator arr[j] as its own sorted sequence of fractions (smallest numerator first). A min-heap always surfaces the globally smallest unextracted fraction; each pop advances one slot in that denominator's sequence, keeping the heap size at most n-1.

1. Seed the heap with the smallest fraction per denominator: (arr[0]/arr[j], 0, j) for each j from 1 to n-1.
2. Pop k-1 times. After each pop of (value, i, j), push (arr[i+1]/arr[j], i+1, j) if i+1 < j — the guard prevents pushing arr[j]/arr[j] = 1, which is not a valid pair.
3. The k-th pop holds the answer.

1import heapq
2
3def kthSmallestPrimeFraction(arr: list[int], k: int) -> list[int]:
4    n = len(arr)
5    # Seed each denominator's sorted column with its smallest fraction (numerator index 0)
6    min_heap = [(arr[0] / arr[j], 0, j) for j in range(1, n)]
7    heapq.heapify(min_heap)
8
9    for _ in range(k - 1):
10        _, numerator_idx, denominator_idx = heapq.heappop(min_heap)
11        next_idx = numerator_idx + 1
12        if next_idx < denominator_idx:  # i must remain strictly less than j
13            heapq.heappush(min_heap, (arr[next_idx] / arr[denominator_idx], next_idx, denominator_idx))
14
15    _, numerator_idx, denominator_idx = heapq.heappop(min_heap)
16    return [arr[numerator_idx], arr[denominator_idx]]

Time: O(n + k log n) — O(n) to build the initial heap, then k pops each costing O(log n).
Space: O(n) — the heap holds at most n-1 entries at any time.

Approach 3 — Binary Search on Value

Binary search on the fraction value in (0, 1). For each candidate midpoint, count how many fractions are ≤ mid using a two-pointer that sweeps across all denominators in O(n). Stop when the count equals k.

1. Initialize lo = 0, hi = 1. Compute mid = (lo + hi) / 2.
2. Sweep denominators j from left to right with a pointer p that never resets between j values (it advances monotonically). For each j, advance p while arr[p] ≤ mid × arr[j]; add p to the total count; update the running maximum fraction.
3. If count < k, raise lo. If count > k, lower hi. If count == k, the tracked maximum is the answer.

1def kthSmallestPrimeFraction(arr: list[int], k: int) -> list[int]:
2    n = len(arr)
3    lo, hi = 0.0, 1.0
4    max_num, max_den = 0, 1
5
6    while hi - lo > 1e-9:
7        mid = (lo + hi) / 2
8        count = 0
9        numerator_ptr = 0  # monotonically non-decreasing across all j iterations
10        max_num, max_den = 0, 1
11
12        for denominator_idx in range(1, n):
13            # Advance while this numerator's fraction is still within the midpoint bound
14            while numerator_ptr < denominator_idx and arr[numerator_ptr] <= mid * arr[denominator_idx]:
15                numerator_ptr += 1
16            count += numerator_ptr  # indices 0..numerator_ptr-1 all qualify for this denominator
17            # The largest qualifying fraction for this denominator is arr[numerator_ptr-1]/arr[j]
18            if numerator_ptr > 0 and arr[numerator_ptr - 1] * max_den > max_num * arr[denominator_idx]:
19                max_num = arr[numerator_ptr - 1]
20                max_den = arr[denominator_idx]
21
22        if count == k:
23            return [max_num, max_den]
24        elif count < k:
25            lo = mid
26        else:
27            hi = mid
28
29    return [max_num, max_den]  # fallback if binary search converges without hitting count == k exactly

Time: O(n log(1/ε)) — roughly 30 binary search iterations each doing an O(n) two-pointer sweep (ε = 1e-9).
Space: O(1) — only counters and pointers; no auxiliary data structure.

Complexity Summary

Common Mistakes

• Forgetting the i+1 < j guard in the heap approach — after popping (i, j) and incrementing to i+1, pushing (i+1, j) when i+1 == j inserts the invalid fraction arr[j]/arr[j] = 1 into the heap, corrupting the k-th result for any subsequent pops.
• Resetting the numerator pointer inside the denominator loop in binary search — the pointer must advance monotonically across all j values; resetting to 0 per j turns the intended O(n) sweep into O(n²) and eliminates the advantage over brute force.
• Off-by-one in the heap loop — the loop runs exactly k-1 times before the final pop; running it k times returns the (k+1)-th element instead.
• Using floating-point in the heap comparator (Java/C++) — comparing arr[a] * arr[b_den] vs arr[b] * arr[a_den] with integers avoids the rare but real ordering bugs that appear when two very close floats compare equal where they should not.
• Missing the maximum update when the numerator pointer doesn't advance — even if the pointer stalls for a particular j, the fraction arr[ptr-1]/arr[j] formed with the current denominator might still be the largest seen so far; checking after the inner while loop (not only inside it) is required.

Related Problems

• Kth Smallest Element in a Sorted Matrix — identical problem shape: k-th smallest from an implicit 2D sorted structure, solved with either a min-heap or binary search on value
• Merge K Sorted Lists — the heap extraction pattern is the same; here each denominator is one of the k sorted sequences to merge
• Split Array Largest Sum — binary search on the answer combined with a linear feasibility count, the same "search on value, verify by counting" technique
• Find K Closest Elements — binary search on the window boundary to locate the k closest values, another example of searching on a value rather than an index
• Capacity to Ship Packages Within D Days — binary search on the answer with a linear check, a clean standalone example of the feasibility-count pattern