#786

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

K-th Smallest Prime Fraction

Find the k-th smallest fraction from a sorted array of unique primes using a binary search over the answer space.

array two pointers binary search sorting heap priority queue

Problem Statement

Given a sorted array arr of unique integers starting with 1 followed by prime numbers, and an integer k, consider all possible fractions arr[i]/arr[j] for 0 <= i < j < arr.length. Your task is to return the k-th smallest fraction in ascending order as an array [arr[i], arr[j]].

The array length satisfies 2 <= arr.length <= 1000, arr[0] == 1, all arr[i] > 0 are prime numbers for i > 0, and the fractions should be considered in ascending numerical value. Return the fraction corresponding to the k-th smallest among all possible fractions.

Examples

Example 1

Input: arr = [1,2,3,5], k = 3

Output: [2,5]

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.

Example 2

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

Output: [1,7]

Example details omitted.

Constraints

2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 104
arr[0] == 1
arr[i] is a prime number for i > 0.
All the numbers of arr are unique and sorted in strictly increasing order.
1 <= k <= arr.length * (arr.length - 1) / 2

Solution Approach

Binary Search Over Fraction Values

Use binary search between 0 and 1 to guess a fraction value. For each midpoint, count how many fractions are less than or equal to it by scanning with two pointers. Adjust the search range based on the count until the exact k-th fraction is determined.

Min-Heap for Fraction Tracking

Initialize a min-heap with fractions starting from the smallest numerators. Pop the smallest fraction k times, each time pushing the next fraction in the row if possible. This ensures efficient retrieval of the k-th smallest without generating all fractions.

Combine Counting with Two Pointers

While performing binary search, maintain two pointers to count the number of fractions less than the current midpoint and track the largest fraction below it. This prevents scanning the entire n^2 fraction space and guarantees O((n+k) * log n) complexity.

Complexity Analysis

Metric	Value
Time	O((n + k) \cdot \log n)
Space	O(n)

Time complexity is O((n + k) * log n) due to binary search iterations and counting with two pointers. Space complexity is O(n) for heap or pointer tracking arrays.

What Interviewers Usually Probe

Asks about efficient fraction counting instead of brute force enumeration.
Hints at using binary search over the value range rather than array indices.
Watches for careful handling of duplicate numerator-denominator pairs and floating-point comparisons.

Common Pitfalls or Variants

Common pitfalls

Generating all n*(n-1)/2 fractions causes TLE for large arrays.
Failing to properly maintain two pointers while counting fractions below the midpoint.
Incorrect floating-point comparisons leading to off-by-one fraction selection.

Follow-up variants

Find the k-th largest fraction instead of smallest using the same binary search approach.
Compute fractions only for a subset of the array with specific numerator or denominator constraints.
Return all fractions less than a given threshold using a similar heap or two-pointer counting method.

FAQ

What is the main pattern used in K-th Smallest Prime Fraction?

The core pattern is binary search over the possible fraction values combined with counting how many fractions are below a guess.

Can I solve this by generating all fractions?

While possible for small arrays, generating all fractions is inefficient and will exceed time limits for larger arrays.

How do I handle floating-point errors in comparisons?

Use careful epsilon comparisons or cross-multiplication to avoid precision issues when comparing arr[i]/arr[j] <= mid.

What data structures optimize k-th fraction retrieval?

A min-heap efficiently tracks the next smallest fractions, and two-pointer scanning avoids full enumeration.

What is the time complexity of the best solution?

Using binary search with two-pointer counting or heap, the time complexity is O((n + k) * log n) and space O(n).

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]
        heapify(h)
        for _ in range(k - 1):
            _, i, j = heappop(h)
            if i + 1 < j:
                heappush(h, (arr[i + 1] / arr[j], i + 1, j))
        return [arr[h[0][1]], arr[h[0][2]]]

Continue Practicing

#658 find k closest elements #825 friends of appropriate ages #826 most profit assigning work