You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
Input: arr = [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, and 2/3. The third fraction is 2/5.
Example 2:
Input: arr = [1,7], k = 1 Output: [1,7]
Constraints:
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i] is a prime number for i > 0.arr are unique and sorted in strictly increasing order.1 <= k <= arr.length * (arr.length - 1) / 2Follow up: Can you solve the problem with better than
O(n2) complexity?Problem Overview: You are given a sorted array of prime numbers where arr[0] = 1. Every pair (arr[i], arr[j]) with i < j forms a fraction arr[i] / arr[j]. The task is to return the k-th smallest fraction among all possible fractions.
Approach 1: Heap / Priority Queue (O(k log n) time, O(n) space)
This method treats each fraction as part of a sorted stream. For a fixed denominator arr[j], fractions arr[0]/arr[j], arr[1]/arr[j], ... increase as the numerator index increases. Initialize a min-heap with fractions where the numerator index starts at 0 and the denominator ranges from 1 to n-1. Each heap entry stores the numerator index and denominator index.
Pop the smallest fraction from the heap. If the numerator can move forward (i.e., i + 1 < j), push the next fraction with numerator i + 1 and the same denominator. Repeat this process k times. The fraction removed on the k-th pop is the answer. The heap always keeps the next smallest candidate across all denominators. This approach relies on a heap (priority queue) to efficiently track the smallest fraction.
Approach 2: Binary Search on Fraction Value (O(n log range) time, O(1) space)
Instead of enumerating fractions, search directly on the possible fraction value between 0 and 1. For a candidate value mid, count how many fractions are less than or equal to mid. Because the array is sorted, you can scan denominators and move a numerator pointer forward to maintain arr[i] / arr[j] ≤ mid. This two-pointer counting step runs in linear time.
While counting, also track the largest fraction that is still ≤ mid. If the count equals k, that fraction is the answer. If the count is smaller than k, move the binary search range up; otherwise move it down. This approach combines binary search with a two pointers sweep to avoid generating all fractions explicitly.
Recommended for interviews: Interviewers typically expect the binary search solution because it shows deeper algorithmic reasoning. The heap approach is easier to implement and demonstrates understanding of ordered streams and priority queues. Mentioning the brute-force idea—generating all fractions and sorting them—shows baseline reasoning, but its O(n² log n) cost does not scale. Implementing either the heap optimization or the binary search technique signals strong problem-solving ability.
This approach uses a min-heap to efficiently find the kth smallest fraction. By iterating through each pair of elements (i, j) in the array where i < j, we can calculate the fraction arr[i]/arr[j] and push it into the heap. The heap is then used to retrieve the k-th smallest element efficiently.
In this C solution, a struct called 'Fraction' is defined to represent a fraction along with its value. The input array is iterated over pairs of indices to compute the fractions which are stored in an array. The array is then sorted based on the fraction values using the quicksort method. Finally, the k-th smallest fraction is returned.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
This approach uses binary search on the value of fractions. By implementing a search over the potential range of fraction values, the algorithm counts how many fractions are less than a given mid-point, narrowing down to the k-th one by manipulating the bounds of the potential fraction values. A two-pointer technique helps count the fractions efficiently.
This C code performs binary searching over the range of fraction values. To find the k-th smallest fraction, the algorithm counts fractions with a value less than a target using two pointers, refining the bounds until the count reaches k.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Heap Approach | Time Complexity: O(n^2 log(n^2)) |
| Binary Search on the Value | Time Complexity: O(n log(max_fraction)) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Generate + Sort Fractions) | O(n² log n) | O(n²) | Useful for understanding the problem or when input size is very small |
| Heap / Priority Queue | O(k log n) | O(n) | Good when k is relatively small and you want to incrementally extract the next smallest fraction |
| Binary Search on Value | O(n log range) | O(1) | Preferred interview solution for sorted arrays when you can count valid fractions efficiently |
K-th Smallest Prime Fraction | Max Heap | Min Heap | Leetcode 786 | codestorywithMIK • codestorywithMIK • 12,397 views views
Watch 9 more video solutions →Practice K-th Smallest Prime Fraction with our built-in code editor and test cases.
Practice on FleetCode