K-th Smallest Prime Fraction
MedPrompt
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 fori > 0.- All the numbers of
arrare unique and sorted in strictly increasing order. 1 <= k <= arr.length * (arr.length - 1) / 2
Follow up: Can you solve the problem with better than
O(n2) complexity?Approaches
3 approaches with complexity analysis and trade-offs.
This approach is the most straightforward and intuitive. The idea is to first generate every possible fraction arr[i] / arr[j] for i < j. These fractions are then stored in a list. After generating all fractions, the list is sorted in ascending order. Finally, the k-th element (at index k-1) of the sorted list is the desired answer.
Algorithm
- Create a list to store fractions. Each fraction can be represented as a pair of integers
[numerator, denominator]. - Iterate through the input array
arrwith two nested loops to generate all possible fractionsarr[i] / arr[j]wherei < j. - For each valid pair
(i, j), add the fraction[arr[i], arr[j]]to the list. - After generating all
N * (N - 1) / 2fractions, sort the list. The comparison between two fractionsa/bandc/dis performed using cross-multiplication (a*dvsc*b) to avoid floating-point precision issues. - The k-th smallest fraction is located at index
k-1in the sorted list. Return this fraction.
Walkthrough
The implementation involves two nested loops to iterate through all pairs of indices (i, j) such that 0 <= i < j < arr.length. For each pair, we form a fraction [arr[i], arr[j]] and add it to a list. Once all fractions are collected, we use a custom comparator to sort them. The comparison a/b < c/d is equivalent to a*d < c*b, which avoids using floating-point arithmetic and its associated precision problems. After sorting, the fraction at index k-1 is the result.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int[] kthSmallestPrimeFraction(int[] arr, int k) { int n = arr.length; List<int[]> fractions = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { fractions.add(new int[]{arr[i], arr[j]}); } } // Sort the fractions using a custom comparator Collections.sort(fractions, (a, b) -> { // Compare a[0]/a[1] and b[0]/b[1] // This is equivalent to comparing a[0]*b[1] and b[0]*a[1] return Integer.compare(a[0] * b[1], b[0] * a[1]); }); return fractions.get(k - 1); }}Complexity
Time
O(N^2 log N). Generating the `O(N^2)` fractions takes `O(N^2)` time. Sorting this list of `O(N^2)` elements takes `O(N^2 log(N^2))`, which simplifies to `O(N^2 log N)`.
Space
O(N^2), where N is the length of `arr`. This is because we need to store all `N * (N - 1) / 2` possible fractions in a list.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct if implemented properly.
Cons
High time complexity, making it potentially too slow for large inputs.
High space complexity, as it requires storing all possible fractions.
This approach improves upon the brute-force method by avoiding the generation and storage of all fractions at once. We can think of the fractions as being organized into N-1 sorted lists, where each list corresponds to a fixed denominator arr[j] and contains fractions arr[0]/arr[j], arr[1]/arr[j], .... The problem then becomes finding the k-th smallest element from these N-1 sorted lists. A min-heap is a perfect data structure for this task.
Algorithm
- Create a min-heap (Priority Queue) that stores pairs of indices
[i, j], representing the fractionarr[i]/arr[j]. The heap is ordered by the value of these fractions. - Initialize the heap by adding the smallest fraction for each possible denominator. For each denominator
arr[j](wherejgoes from 1 toN-1), the smallest fraction isarr[0]/arr[j]. So, push the index pairs[0, j]forj = 1, ..., N-1into the heap. - Extract the minimum element from the heap
ktimes. - For each extracted element
[i, j], if there is a next larger fraction with the same denominatorarr[j](i.e.,arr[i+1]/arr[j]), add its index pair[i+1, j]to the heap. - The
k-th element extracted from the heap corresponds to the k-th smallest fraction. Return[arr[i], arr[j]]for this element.
Walkthrough
We use a min-heap to efficiently manage the smallest current element from each of the conceptual sorted lists. The heap will store pairs of indices [i, j] corresponding to the fraction arr[i]/arr[j]. The comparison logic for the heap will be based on the fraction's value, using cross-multiplication to maintain precision.
Initially, we populate the heap with the first (and smallest) element from each of the N-1 lists: arr[0]/arr[1], arr[0]/arr[2], ..., arr[0]/arr[N-1]. Then, we repeatedly extract the minimum fraction from the heap. After extracting a fraction arr[i]/arr[j], we add the next fraction from the same list, arr[i+1]/arr[j], to the heap (if it exists). We repeat this process k times. The k-th fraction extracted is our answer.
import java.util.PriorityQueue; class Solution { public int[] kthSmallestPrimeFraction(int[] arr, int k) { int n = arr.length; // Min-heap stores {numerator_index, denominator_index} PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(arr[a[0]] * arr[b[1]], arr[b[0]] * arr[a[1]])); // Initially, push the smallest fraction from each 'column' (denominator) // The smallest fraction for denominator arr[j] is arr[0]/arr[j] for (int j = 1; j < n; j++) { pq.offer(new int[]{0, j}); } // Extract the smallest element k-1 times for (int count = 0; count < k - 1; count++) { int[] top = pq.poll(); int i = top[0]; int j = top[1]; // If there's a next element in the same column, add it to the heap if (i + 1 < j) { pq.offer(new int[]{i + 1, j}); } } // The top of the heap is now the k-th smallest fraction int[] resultIndices = pq.poll(); return new int[]{arr[resultIndices[0]], arr[resultIndices[1]]}; }}Complexity
Time
O((N + K) log N). Initializing the heap takes `O(N log N)`. Each of the `K` extractions and subsequent insertions takes `O(log N)`. If `K` is small, this is efficient. If `K` is `O(N^2)`, the complexity approaches `O(N^2 log N)`.
Space
O(N), where N is the length of `arr`. The heap stores at most `N-1` elements.
Trade-offs
Pros
Significant improvement in space complexity over the brute-force approach.
Generally faster than brute-force, especially for smaller values of
k.
Cons
The time complexity can be slow if
kis large, approachingO(N^2).
This is the most optimal approach, leveraging the fact that we are looking for a k-th ordered element. Instead of generating fractions, we can binary search for the value of the k-th fraction. The values of all fractions are in the range [0, 1]. For any guessed value x in this range, we can efficiently determine how many fractions are smaller than or equal to x. This information allows us to narrow down the search range for the value, similar to a standard binary search on a sorted array.
Algorithm
- The values of the fractions
arr[i]/arr[j]are all between 0 and 1. We can binary search for the value of the k-th smallest fraction in this range. - For a given
midvalue from the binary search, we need a function to count how many fractions are less than or equal tomid. Let's call thiscount(mid). count(mid)can be implemented efficiently inO(N)time using a two-pointer technique. We iterate through denominatorsarr[j]and for each, find how many numeratorsarr[i]satisfyarr[i] <= mid * arr[j].- While counting, we also keep track of the largest fraction encountered that is still less than or equal to
mid. Let this bep/q. - Based on the
count:- If
count < k, the target fraction's value is larger thanmid, so we search in(mid, high]. - If
count >= k,midis a potential answer or too high. The answer is in[low, mid]. We store[p, q]as our current best answer and continue searching in[low, mid]to find an even smaller value.
- If
- The binary search continues until the range
[low, high]is sufficiently small, and the stored[p, q]will be the k-th smallest fraction.
Walkthrough
We define a search space for the fraction's value, [low, high], initialized to [0.0, 1.0]. In each step of the binary search, we pick a mid value. We then need to count how many pairs (i, j) with i < j satisfy arr[i] / arr[j] <= mid. This is equivalent to arr[i] <= mid * arr[j].
This counting can be done in O(N) time. We iterate through j from 1 to N-1. For each j, we find the count of i < j that satisfy the condition. Since arr is sorted, as j increases, the upper bound for arr[i] (mid * arr[j]) also increases. This monotonicity allows us to use a second pointer for i that only moves forward, leading to an overall linear time complexity for the count.
During the counting process for a given mid, we also track the maximum fraction found that is less than or equal to mid. If the total count is less than k, we know our mid is too small and we must search for a larger value (low = mid). If the count is k or more, mid is a candidate for our answer's value (or is too large), so we record the maximum fraction we found as a potential answer and try to find a better (smaller) value (high = mid).
class Solution { public int[] kthSmallestPrimeFraction(int[] arr, int k) { int n = arr.length; double low = 0.0, high = 1.0; int[] ans = new int[2]; while (high - low > 1e-9) { double mid = low + (high - low) / 2.0; int count = 0; int p = 0, q = 1; // To store the max fraction <= mid int i = 0; for (int j = 1; j < n; j++) { while (i < j && arr[i] < mid * arr[j]) { i++; } count += i; if (i > 0 && arr[i - 1] * q > p * arr[j]) { p = arr[i - 1]; q = arr[j]; } } if (count < k) { low = mid; } else { ans[0] = p; ans[1] = q; high = mid; } } return ans; }}Complexity
Time
O(N log W), where N is the length of the array and W is the range of values. The `log W` factor represents the number of binary search iterations, which is effectively constant due to the required precision (e.g., `log(10^9)` is about 30). The counting step inside the loop takes `O(N)`. Therefore, the overall time complexity is effectively linear, `O(N)`.
Space
O(1). The algorithm only requires a few variables to maintain the state of the binary search and the two-pointer count, regardless of the input size.
Trade-offs
Pros
Extremely efficient time complexity.
Optimal space complexity.
Cons
More complex to conceptualize and implement correctly.
Requires careful handling of floating-point numbers and the binary search termination condition.
Solutions
Solution
class Solution {public int[] kthSmallestPrimeFraction(int[] arr, int k) { int n = arr.length; Queue<Frac> pq = new PriorityQueue<>(); for (int i = 1; i < n; i++) { pq.offer(new Frac(1, arr[i], 0, i)); } for (int i = 1; i < k; i++) { Frac f = pq.poll(); if (f.i + 1 < f.j) { pq.offer(new Frac(arr[f.i + 1], arr[f.j], f.i + 1, f.j)); } } Frac f = pq.peek(); return new int[]{f.x, f.y}; } static class Frac implements Comparable { int x, y, i, j; public Frac(int x, int y, int i, int j) { this.x = x; this.y = y; this.i = i; this.j = j; } @Override public int compareTo(Object o) { return x * ((Frac)o).y - ((Frac)o).x * y; } }}class Solution {public: vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k) { using pii = pair<int, int>; int n = arr.size(); auto cmp = [&](const pii &a, const pii &b) { return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second]; }; priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp); for (int i = 1; i < n; ++i) { pq.push({0, i}); } for (int i = 1; i < k; ++i) { pii f = pq.top(); pq.pop(); if (f.first + 1 < f.second) { pq.push({f.first + 1, f.second}); } } return {arr[pq.top().first], arr[pq.top().second]}; }};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]]]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.