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) / 2O(n2) complexity?The K-th Smallest Prime Fraction problem asks you to find the k-th smallest fraction formed by arr[i] / arr[j] where i < j and the array contains sorted prime numbers. A brute-force approach would generate all possible fractions and sort them, but this is inefficient for larger inputs.
A more optimal method uses a min-heap (priority queue). Start by inserting fractions with the smallest numerators for each denominator into the heap, then repeatedly extract the smallest fraction and push the next candidate from the same denominator sequence. This efficiently simulates the sorted order of fractions.
Another advanced technique applies binary search on the fraction value range between 0 and 1. For each midpoint, count how many fractions are smaller using a two-pointer strategy. This allows narrowing down the exact k-th fraction without explicitly listing all possibilities.
These approaches significantly reduce computation compared to brute force, with heap and binary-search methods providing scalable solutions for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Min Heap (Priority Queue) | O(k log n) | O(n) |
| Binary Search + Two Pointers | O(n log 1/ε) | O(1) |
| Brute Force with Sorting | O(n² log n) | O(n²) |
NeetCode
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.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 double value;
6 int numerator;
7 int denominator;
8} Fraction;
9
10int cmp(const void* a, const void* b) {
11 Fraction* fa = (Fraction*)a;
12 Fraction* fb = (Fraction*)b;
13 return (fa->value > fb->value) - (fa->value < fb->value);
14}
15
16int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize){
17 Fraction* fractions = (Fraction*)malloc(arrSize * arrSize * sizeof(Fraction));
18 int index = 0;
19 for (int i = 0; i < arrSize; ++i) {
20 for (int j = i + 1; j < arrSize; ++j) {
21 fractions[index].value = (double)arr[i] / arr[j];
22 fractions[index].numerator = arr[i];
23 fractions[index].denominator = arr[j];
24 ++index;
25 }
26 }
27 qsort(fractions, index, sizeof(Fraction), cmp);
28 int* result = (int*)malloc(2 * sizeof(int));
29 result[0] = fractions[k - 1].numerator;
30 result[1] = fractions[k - 1].denominator;
31 *returnSize = 2;
32 free(fractions);
33 return result;
34}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.
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.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem is common in technical interviews because it combines multiple concepts such as heaps, binary search, and two-pointer techniques. It tests a candidate's ability to optimize beyond brute-force enumeration.
One of the most efficient approaches uses binary search on the possible fraction range between 0 and 1. For each mid value, a two-pointer technique counts how many fractions are smaller and tracks the best candidate. This avoids generating all fractions explicitly and performs well for large arrays.
Binary search works because the fraction values lie in a continuous range between 0 and 1. By checking how many fractions are less than a chosen midpoint, the algorithm can determine whether the k-th fraction lies to the left or right of that value.
A min-heap (priority queue) is commonly used to efficiently track the next smallest fraction. By pushing candidate fractions and always extracting the smallest one, the algorithm simulates a sorted order without computing every fraction beforehand.
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.