Skip to main content

786. Kth Smallest Prime Fraction

medium

Among all fractions arr[i]/arr[j] with i < j, return the kth smallest. The min-heap solution is the natural fit — and the binary-search-on-value alternative is a great follow-up question.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. 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].

Constraints

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 10^4
  • 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

Examples

Example 1

Input
arr = [1,2,3,5], k = 3
Output
[2,5]

Explanation: Fractions: 1/2, 1/3, 1/5, 2/3, 2/5, 3/5. Sorted: 1/5, 1/3, 2/5, 1/2, 2/3, 3/5. The 3rd is 2/5.

Example 2

Input
arr = [1,7], k = 1
Output
[1,7]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: enumerate all O(n^2) fractions, sort, return the kth. O(n^2 log n). Works for n=1000 but cleaner solutions exist.

Hint 2

Observation: for each fixed denominator arr[j], numerators arr[0..j-1] are in increasing order. So arr[0]/arr[j] is the smallest fraction with denominator arr[j].

Hint 3

Push (arr[0]/arr[j], 0, j) for each j into a min-heap. Pop k-1 times; after each pop of (i, j), push (i+1, j) if i+1 < j.

Hint 4

Alternative: binary-search on the fraction value. Count how many fractions <= mid via a two-pointer sweep; narrow until count == k.

Solution approach

Reveal approach

Min-heap approach. Initialize a min-heap with one entry per denominator: (arr[0] / arr[j], 0, j) for j in 1..n-1. The heap compares by the fraction value. Pop the smallest k-1 times. After popping (i, j), push (arr[i+1] / arr[j], i+1, j) if i+1 < j — that's the next-smallest fraction with the same denominator. After k-1 pops, the heap's top is the kth smallest; return [arr[i], arr[j]]. The invariant: the heap always contains the next unconsumed fraction for each denominator that still has one. Complexity: O(k log n) time and O(n) heap space. Alternative path (worth knowing): binary-search on the fraction value in [0, 1]. Define count(x) = number of fractions <= x and track the largest fraction <= x. Compute count(x) in O(n) via two pointers. Binary-search the smallest x with count(x) >= k. O(n log(maxVal^2 / precision)) — useful when n is large but k is also large. Pick min-heap for the canonical interview answer.

Complexity

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

Related patterns

  • heap
  • priority-queue
  • k-way-merge

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon
  • Meta

More Heaps practice problems

See all Heaps problems →