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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Kth Smallest Prime Fraction and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →