786. K-th Smallest Prime Fraction

786

MediumHeap and Priority QueueMin-heap over candidate fractionsK-way merge of sorted fraction streams

K-th Smallest Prime Fraction

Given a strictly increasing array arr consisting of 1 and distinct prime numbers, consider every fraction arr[i]/arr[j] with i < j. Return the kth smallest such fraction as a two-element array [arr[i], arr[j]].

Open official problem prompt ↗

In plain English

Find the kth smallest value among all arr[i]/arr[j] fractions without materializing and sorting the O(n^2) list of them.

Picture it like this

Merging many already-sorted playlists into one ordered stream: peek the current front song of each playlist, always take the globally earliest, and pull the next song from whichever playlist you just drew from.

Example

Input: arr = [1, 2, 3, 5], k = 3
Output: [2, 5]
Why: Sorted fractions are 1/5, 1/3, 2/5, 1/2, 3/5, 2/3; the 3rd smallest is 2/5, returned as [2, 5].

Constraints

2 <= arr.length <= 10001 <= arr[i] <= 3 * 10^4arr[0] == 1arr[i] for i > 0 is a prime numberAll numbers in arr are unique and sorted in strictly increasing order1 <= k <= arr.length * (arr.length - 1) / 2

Pattern lesson

See the pattern, then code

K-way merge of sorted fraction streams

↗

Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. For a fixed numerator arr[i], the fraction shrinks as the denominator grows, so arr[i]/arr[n-1] is the smallest fraction with that numerator. Seed the heap with one such smallest fraction per numerator, then repeatedly pop the global minimum and advance that numerator to the next-smaller denominator.

New words, made simpleKnow these before the algorithm

K-way merge: Combining several sorted sequences into one sorted order by repeatedly taking the smallest current head.
Candidate frontier: The set of next-possible smallest fractions currently held in the heap, one per active numerator.
Numerator/denominator index: Positions i and j in arr with i < j defining the fraction arr[i]/arr[j].

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate and sort all fractions

Quadratic memory and time; wasteful when k is small relative to all pairs.

Build all n(n-1)/2 fractions, sort them, index k-1.

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

Best choiceMin-heap k-way merge

Only ever holds n candidates and touches k of them.

Keep the smallest fraction per numerator on a heap and pop k-1 times, advancing denominators.

Time O((n + k) log n)Space O(n)

Binary search on the fraction value

Even faster and O(1) space, but trickier to derive; the heap is the natural pattern-based answer.

Binary search a threshold and count fractions below it, tightening to the kth.

Time O(n log(max^2))Space O(1)

The rule we keep true

Invariant

The heap always contains, for each numerator that has not been exhausted, the smallest fraction with that numerator not yet emitted; hence the heap root is the smallest fraction not yet popped.

Why this is correct

Reasoning

For a fixed numerator arr[i], fractions strictly decrease as the denominator index decreases from n-1 downward, so each numerator forms its own sorted stream whose current head sits in the heap. Popping the global minimum and inserting the next head from that stream is exactly a k-way merge, which yields fractions in nondecreasing order; the kth thing produced is the kth smallest.

The algorithm in three movesSay these aloud before coding

1Seed a min-heap with (arr[i]/arr[n-1], i, n-1) for every numerator index i

seed = [1/5, 2/5, 3/5]

2Pop the smallest fraction k-1 times

pop 1/5 -> push 1/3; pop 1/3 -> push 1/2

3After each pop, if a smaller denominator index (still > i) exists, push (arr[i]/arr[j-1], i, j-1)

root now 2/5 -> [2,5]

4The heap root after k-1 pops is the kth smallest — return its numerator and denominator values

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1/50

1/31

2/52

1/23

3/54

2/35

1 · Readarr=[1,2,3,5]

2 · AskSmallest per numerator

3 · Update stateheap = {1/5, 2/5, 3/5}

4 · Resultglobal min is 1/5

Key takeaway

Fractions in sorted order; after two pops the heap root is the 3rd smallest, 2/5.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Seed the frontier
For every numerator index i, the pair with the largest denominator arr[n-1] is that numerator's smallest fraction; heapify these n-1 candidates.
2
Lines 9-12Pop and advance
Pop the smallest fraction k-1 times; each pop pushes the same numerator paired with the next-smaller denominator, as long as that denominator index stays above i.
3
Lines 13Read the answer
After k-1 pops the heap root is the kth smallest fraction; return its stored numerator and denominator values.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k = 1 returns the single smallest fraction arr[0]/arr[n-1]
k equal to the total number of pairs returns the largest fraction
arr of length 2 has exactly one fraction
fractions that are numerically close but never equal (all values distinct)

Common beginner mistakes

Comparing fractions with integer division instead of float or cross-multiplication, collapsing distinct values to 0
Advancing the denominator past the numerator (j must stay > i)
Off-by-one on the loop count — pop exactly k-1 times, then read the root
Storing the fraction value only and losing the indices needed for the [num, den] answer

Check your understanding

Why seed the heap with the largest denominator for each numerator rather than the smallest?

K-th Smallest Prime Fraction

K-th Smallest Prime Fraction

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Heap and Priority Queue