786. K-th Smallest Prime Fraction - Solution

Q: Is K-th Smallest Prime Fraction easy or hard?

The problem is rated Medium on LeetCode with an acceptance rate around 69%. The heap solution is relatively straightforward once you recognize the ordered structure of fractions, while the binary search on value technique requires deeper understanding of two-pointer counting.

Q: K-th Smallest Prime Fraction Python/Java solution

Python and Java implementations typically use a priority queue for the heap approach or a while-loop binary search for the optimal method. The heap solution stores numerator and denominator indices, while the binary search solution scans the array each iteration to count valid fractions.

Q: What is the best approach for K-th Smallest Prime Fraction?

The most efficient interview solution uses binary search on the fraction value combined with a two-pointer counting technique. Each iteration counts how many fractions are ≤ mid in O(n) time, leading to overall complexity of O(n log range) with O(1) extra space. A heap-based solution with O(k log n) time is also common and easier to implement.

Q: How to solve K-th Smallest Prime Fraction in O(n log range)?

Perform binary search on the possible fraction values between 0 and 1. For each mid value, count how many fractions arr[i]/arr[j] are ≤ mid using a two-pointer scan across the sorted array. Track the maximum fraction below mid during the scan. Adjust the search range until the count equals k.

Q: Is K-th Smallest Prime Fraction asked at Google/Amazon/Meta?

This problem pattern appears in interviews at large tech companies because it combines binary search on answer with heap-based ordering. Variants involving k-th smallest pair, fraction ordering, or sorted matrix search have been reported in Google, Amazon, and Meta interview preparation sets.

Q: What data structure is used in K-th Smallest Prime Fraction?

Two main structures are used: a min-heap (priority queue) to always extract the smallest fraction candidate, and two pointers for counting fractions during binary search. The sorted array property is critical for both methods because it guarantees monotonic fraction ordering.

Q: What is the time complexity of K-th Smallest Prime Fraction?

The heap approach runs in O(k log n) time because each heap operation costs log n and is performed k times. The binary search method runs in O(n log range) time where each iteration scans the array once to count valid fractions. Space complexity is O(n) for the heap solution and O(1) for binary search.

The problem

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 k^th 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 <= 1000
1 <= arr[i] <= 3 * 10⁴
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

Follow up: Can you solve the problem with better than O(n²) complexity?

Approach overview

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 1: Heap Approach

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.

Python

import heapq

class Solution:
    def kthSmallestPrimeFraction(self, arr, k):
        n = len(arr)
        pq = [(arr[i] / arr[j], i, j) for i in range(n) for j in range(i + 1, n)]
        heapq.heapify(pq)
        while k > 1:
            heapq.heappop(pq)
            k -= 1
        return pq[0][1], pq[0][2]

Java

import java.util.PriorityQueue;

public class KthSmallestPrimeFraction {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);
        for (int i = 0; i < n - 1; i++) {
            pq.offer(new int[]{i, n - 1});
        }
        int[] result = new int[2];
        while (k-- > 0) {
            result = pq.poll();
            if (result[1] - 1 > result[0]) {
                pq.offer(new int[]{result[0], result[1] - 1});
            }
        }
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

C++

#include <vector>
#include <queue>
#include <utility>

using namespace std;

vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    int n = arr.size();
    auto cmp = [&](pair<int, int>& a, pair<int, int>& b) {
        return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second];
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    for (int i = 0; i < n; ++i) pq.emplace(i, n - 1);
    pair<int, int> result;
    while (k--) {
        result = pq.top();
        pq.pop();
        if (result.second - 1 > result.first) {
            pq.emplace(result.first, result.second - 1);
        }
    }
    return {arr[result.first], arr[result.second]};
}

JavaScript

var kthSmallestPrimeFraction = function(arr, k) {
    let n = arr.length;
    let heap = new MinPriorityQueue({
        compare: (a, b) => arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]
    });

    for(let i = 0; i < n; i++) {
        heap.enqueue([i, n - 1]);
    }
    let res = null;
    while(k--) {
        res = heap.dequeue().element;
        if(res[1] - 1 > res[0]) heap.enqueue([res[0], res[1] - 1]);
    }
    return [arr[res[0]], arr[res[1]]];
};

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double value;
    int numerator;
    int denominator;
} Fraction;

int cmp(const void* a, const void* b) {
    Fraction* fa = (Fraction*)a;
    Fraction* fb = (Fraction*)b;
    return (fa->value > fb->value) - (fa->value < fb->value);
}

int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize){
    Fraction* fractions = (Fraction*)malloc(arrSize * arrSize * sizeof(Fraction));
    int index = 0;
    for (int i = 0; i < arrSize; ++i) {
        for (int j = i + 1; j < arrSize; ++j) {
            fractions[index].value = (double)arr[i] / arr[j];
            fractions[index].numerator = arr[i];
            fractions[index].denominator = arr[j];
            ++index;
        }
    }
    qsort(fractions, index, sizeof(Fraction), cmp);
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = fractions[k - 1].numerator;
    result[1] = fractions[k - 1].denominator;
    *returnSize = 2;
    free(fractions);
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        var pq = new PriorityQueue<(double, int, int), double>();
        for (int i = 0; i < arr.Length; ++i)
            for (int j = i + 1; j < arr.Length; ++j)
                pq.Enqueue((arr[i] / (double)arr[j], i, j), arr[i] / (double)arr[j]);
        while (--k > 0)
            pq.Dequeue();
        var result = pq.Dequeue();
        return new int[] { arr[result.Item2], arr[result.Item3] };
    }
}

Python uses a min-heap for k operations. All fractions are calculated and stored in the priority queue. We pop the smallest fraction k times to achieve the desired k-th smallest fraction.

Complexity

Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)

Try this approach in the editor

Approach 2: Binary Search on the Value

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.

Python

class Solution:
    def kthSmallestPrimeFraction(self, arr, k):
        low, high = 0.0, 1.0
        n = len(arr)
        while high - low > 1e-9:
            mid = (low + high) / 2
            p = q = -1
            max_fraction = 0.0
            total = i = 0
            for j in range(1, n):
                while i < j and arr[i] < arr[j] * mid:
                    i += 1
                total += i
                if i > 0:
                    fraction = arr[i - 1] / arr[j]
                    if fraction > max_fraction:
                        max_fraction = fraction
                        p, q = arr[i - 1], arr[j]
            if total < k:
                low = mid
            else:
                high = mid
                result = [p, q]
        return result

Java

public class KthSmallestPrimeFraction {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double lo = 0.0, hi = 1.0;
        int n = arr.length;
        int[] result = new int[2];

        while (hi - lo > 1e-9) {
            double mid = (lo + hi) / 2;
            double maxFraction = 0.0;
            int count = 0, numerator = 0, denominator = 1;
            for (int i = 0, j = 1; j < n; j++) {
                while (i < j && arr[i] < arr[j] * mid)
                    i++;
                count += i;
                if (i > 0) {
                    double fraction = (double) arr[i - 1] / arr[j];
                    if (fraction > maxFraction) {
                        maxFraction = fraction;
                        numerator = arr[i - 1];
                        denominator = arr[j];
                    }
                }
            }
            if (count < k) lo = mid;
            else {
                hi = mid;
                result[0] = numerator;
                result[1] = denominator;
            }
        }
        return result;
    }
}

C++

#include <vector>
using namespace std;

vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    double lo = 0.0, hi = 1.0, mid;
    int n = arr.size();
    vector<int> result(2);
    
    while (hi - lo > 1e-9) {
        mid = (lo + hi) / 2;
        double maxFraction = 0;
        int numerator = 0, denominator = 1;
        int count = 0;

        for (int i = 0, j = 1; j < n; ++j) {
            while (i < j && arr[i] < arr[j] * mid)
                i++;
            count += i;
            if (i > 0) {
                double fraction = (double)arr[i - 1] / arr[j];
                if (fraction > maxFraction) {
                    maxFraction = fraction;
                    numerator = arr[i - 1];
                    denominator = arr[j];
                }
            }
        }

        if (count < k)
            lo = mid;
        else {
            hi = mid;
            result[0] = numerator;
            result[1] = denominator;
        }
    }
    return result;
}

JavaScript

var kthSmallestPrimeFraction = function(arr, k) {
    let low = 0.0, high = 1.0;
    let result = [];

    while (high - low > 1e-9) {
        let mid = (low + high) / 2;
        let count = 0, i = 0, numerator = 0, denominator = 1;
        let maxFraction = 0.0;

        for (let j = 1; j < arr.length; j++) {
            while (i < j && arr[i] < arr[j] * mid) i++;
            count += i;
            if (i > 0) {
                let fraction = arr[i - 1] / arr[j];
                if (fraction > maxFraction) {
                    maxFraction = fraction;
                    numerator = arr[i - 1];
                    denominator = arr[j];
                }
            }
        }

        if (count < k) {
            low = mid;
        } else {
            high = mid;
            result = [numerator, denominator];
        }
    }
    return result;
};

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize){
    double lo = 0, hi = 1, mid;
    int n = arrSize;
    int* result = (int*)malloc(2 * sizeof(int));
    
    while (hi - lo > 1e-9) {
        mid = (lo + hi) / 2;
        double maxFraction = 0;
        int num = 0, denom = 1;
        int count = 0;

        for (int i = 0, j = 1; j < n; ++j) {
            while (arr[i] < arr[j] * mid)
                i++;
            count += i;
            
            if (i > 0) {
                double fraction = (double)arr[i - 1] / arr[j];
                if (fraction > maxFraction) {
                    maxFraction = fraction;
                    num = arr[i - 1];
                    denom = arr[j];
                }
            }
        }

        if (count < k)
            lo = mid;
        else {
            hi = mid;
            result[0] = num;
            result[1] = denom;
        }
    }
    *returnSize = 2;
    return result;
}

using System;

public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        double lo = 0.0, hi = 1.0;
        while (hi - lo > 1e-9) {
            double mid = (lo + hi) / 2.0;
            int count = 0;
            int p = 0, q = 1;
            double maxFraction = 0.0;
            int i = 0;
            for (int j = 1; j < arr.Length; j++) {
                while (i < j && arr[i] < arr[j] * mid) i++;
                count += i;
                if (i > 0) {
                    double fraction = (double)arr[i - 1] / arr[j];
                    if (fraction > maxFraction) {
                        maxFraction = fraction;
                        p = arr[i - 1];
                        q = arr[j];
                    }
                }
            }
            if (count < k) lo = mid;
            else {
                hi = mid;
                result[0] = p;
                result[1] = q;
            }
        }
        return result;
    }
}

With Python, binary search narrows the range of potential fraction values. Using two-pointers enables a count of fractions less than a midpoint, helping binary search converge on the k-th smallest.

Complexity

Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

type frac struct{ x, y, i, j int }
type hp []frac

func (a hp) Len() int           { return len(a) }
func (a hp) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool { return a[i].x*a[j].y < a[j].x*a[i].y }
func (a *hp) Push(x any)        { *a = append(*a, x.(frac)) }
func (a *hp) Pop() any          { l := len(*a); tmp := (*a)[l-1]; *a = (*a)[:l-1]; return tmp }

func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	h := make(hp, 0, n-1)
	for i := 1; i < n; i++ {
		h = append(h, frac{1, arr[i], 0, i})
	}
	heap.Init(&h)
	for i := 1; i < k; i++ {
		f := heap.Pop(&h).(frac)
		if f.i+1 < f.j {
			heap.Push(&h, frac{arr[f.i+1], arr[f.j], f.i + 1, f.j})
		}
	}
	return []int{h[0].x, h[0].y}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Heap Approach	Time Complexity: O(n^2 log(n^2)) Space Complexity: O(n^2)
Binary Search on the Value	Time Complexity: O(n log(max_fraction)) Space Complexity: O(1)
Default Approach	–

Complexity analysis

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

Frequently asked questions

Is K-th Smallest Prime Fraction easy or hard?

The problem is rated Medium on LeetCode with an acceptance rate around 69%. The heap solution is relatively straightforward once you recognize the ordered structure of fractions, while the binary search on value technique requires deeper understanding of two-pointer counting.

K-th Smallest Prime Fraction Python/Java solution

Python and Java implementations typically use a priority queue for the heap approach or a while-loop binary search for the optimal method. The heap solution stores numerator and denominator indices, while the binary search solution scans the array each iteration to count valid fractions.

What is the best approach for K-th Smallest Prime Fraction?

The most efficient interview solution uses binary search on the fraction value combined with a two-pointer counting technique. Each iteration counts how many fractions are ≤ mid in O(n) time, leading to overall complexity of O(n log range) with O(1) extra space. A heap-based solution with O(k log n) time is also common and easier to implement.

How to solve K-th Smallest Prime Fraction in O(n log range)?

Perform binary search on the possible fraction values between 0 and 1. For each mid value, count how many fractions arr[i]/arr[j] are ≤ mid using a two-pointer scan across the sorted array. Track the maximum fraction below mid during the scan. Adjust the search range until the count equals k.

Is K-th Smallest Prime Fraction asked at Google/Amazon/Meta?

This problem pattern appears in interviews at large tech companies because it combines binary search on answer with heap-based ordering. Variants involving k-th smallest pair, fraction ordering, or sorted matrix search have been reported in Google, Amazon, and Meta interview preparation sets.

What data structure is used in K-th Smallest Prime Fraction?

Two main structures are used: a min-heap (priority queue) to always extract the smallest fraction candidate, and two pointers for counting fractions during binary search. The sorted array property is critical for both methods because it guarantees monotonic fraction ordering.

What is the time complexity of K-th Smallest Prime Fraction?

The heap approach runs in O(k log n) time because each heap operation costs log n and is performed k times. The binary search method runs in O(n log range) time where each iteration scans the array once to count valid fractions. Space complexity is O(n) for the heap solution and O(1) for binary search.

K-th Smallest Prime Fraction solution and explanation

The problem

Approach overview

Approach 1: Heap Approach

Approach 2: Binary Search on the Value

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

K-th Smallest Prime Fraction solution and explanation

The problem

Approach overview

Approach 1: Heap Approach

Approach 2: Binary Search on the Value

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems