K-th Smallest Prime Fraction - Solution & Explanation

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.

MediumArray Two Pointers Binary Search Sorting15 min readAsked at: Ponyai

Practice this problem

Problem Statement

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go

Python

Java

C++

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	—

Detailed 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

Video Solution

K-th Smallest Prime Fraction | Max Heap | Min Heap | Leetcode 786 | codestorywithMIK • codestorywithMIK • 13,372 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice K-th Smallest Prime Fraction with our built-in code editor and test cases.

Practice on FleetCode

Find K-th Smallest Pair Distance

Kth Smallest Element in a Sorted Matrix

Problem Info

DifficultyMedium

Acceptance69.0%

Approaches3

Reading time15 min

Asked at

Ponyai

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Heap Approach

Code

Complexity

Approach 2: Binary Search on the Value

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents