Coding Interview PatternsKth Smallest Prime Fraction
MediumK-way Merge
Kth Smallest Prime Fraction
Explanation & Solution
Description
You are given a sorted array arr of 1 and prime numbers, and an integer k.
For every pair of indices i < j, consider the fraction arr[i] / arr[j]. Return the kth smallest such fraction as an array [arr[i], arr[j]].
Input:arr = [1,2,3,5], k = 3
0
1
1
2
2
3
3
5
Output:[2,5]
0
2
1
5
Explanation: The fractions in order are: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The 3rd is 2/5.
Constraints
2 <= arr.length <= 10001 == arr[0]arr[i]is prime fori > 0- All elements of
arrare unique. 1 <= k <= arr.length * (arr.length - 1) / 2
Approach
K-way Merge pattern
1. Model as K Sorted Lists
- For each denominator index
j(from 1 to n-1), the fractionsarr[0]/arr[j], arr[1]/arr[j], ..., arr[j-1]/arr[j]form an ascending sequence - Seed the min-heap with the smallest fraction from each such column:
arr[0] / arr[j]for everyj
2. Heapify
- Build the heap in O(n) from the seeded entries
[fraction, numeratorIndex, denominatorIndex]
3. Extract k-1 Times
- Pop the minimum
k-1times, each time replacing it with the next fraction in the same column (sameqi, incrementpi) - If
pi + 1 == qithere are no more fractions in that column — remove it
4. Return the kth Minimum
- After k-1 pops, the heap root is the kth smallest fraction
- Return
[arr[pi], arr[qi]]
Key Insight
- Each column
arr[*]/arr[j]is sorted ascending (numerators increase while denominator is fixed), so this is a classic k-way merge on n virtual sorted sequences
Time
O(n + k log n)O(n) to heapify, O(log n) per extractionSpace
O(n) for the heapVisualization
Input:
[1, 2, 3, 5], k = 3
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps