Watch 10 video solutions for K-th Smallest Prime Fraction, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by codestorywithMIK has 12,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |