K th smallest prime fraction

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

69.0% acceptance

Feb 21, 2026

2133

121

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 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].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/*
 * 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 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].
 * 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 * 104
 * 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(n2) complexity?
 */
impl Solution {
  pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
    let n = arr.len();
    let mut fracs: Vec<(i32, i32)> = Vec::with_capacity(n * (n - 1) / 2);
    for i in 0..n {
      for j in i + 1..n {
        fracs.push((arr[i], arr[j]));
      }
    }
    fracs.sort_by(|&(a, b), &(c, d)| (a as i64 * d as i64).cmp(&(c as i64 * b as i64)));
    vec![fracs[k as usize - 1].0, fracs[k as usize - 1].1]
  }
}