Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Kth Smallest Prime Fraction

Kth Smallest Prime Fraction

Master this topic with zero to advance depth.

Kth Smallest Prime Fraction

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

Visual Representation

arr = [1, 2, 3, 5], k = 3 All fractions: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3 Sorted: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3 3rd smallest: 2/5 Heap strategy: Start with 1/5, 1/3, 1/2. Pop smallest (1/5), push next numerator: 2/5. Pop smallest (1/3), push next: 2/3. Pop smallest (2/5). This is the 3rd pop -> Result [2, 5].
Medium

Examples

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

Level I: Brute Force - Generate and Sort

Intuition

Generate all possible fractions arr[i] / arr[j] where i < j. Store them in a list, sort the list by fraction value, and return the kth element. Simple but slow for large arrays.

⏱ O(N^2 log N) where N is the length of the array. We generate N^2 fractions and sort them.💾 O(N^2) to store all fractions

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Fractions: 1/2, 1/3, 1/5, 2/3, 2/5, 3/5 Values: 0.5, 0.33, 0.2, 0.66, 0.4, 0.6 Sorted values: 0.2(1/5), 0.33(1/3), 0.4(2/5), 0.5(1/2), 0.6(3/5), 0.66(2/3) 3rd smallest: [2, 5].

java
import java.util.*;

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        List<int[]> fractions = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                fractions.add(new int[]{arr[i], arr[j]});
            }
        }
        
        Collections.sort(fractions, (a, b) -> Double.compare((double)a[0]/a[1], (double)b[0]/b[1]));
        return fractions.get(k - 1);
    }
}
Approach 2

Level II: Binary Search on Value Range

Intuition

The value of any fraction is between 0 and 1. We can binary search for a value X such that there are exactly k fractions smaller than or equal to X. For a given X, we can count how many fractions satisfy arr[i] / arr[j] <= X (or arr[i] <= X * arr[j]) in O(N)O(N) time using two pointers.

⏱ O(N log(1/ε)) where ε is the precision. Each count step is O(N).💾 O(1) extra space

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Low=0, High=1, Mid=0.5. Count <= 0.5: 1/2, 1/3, 1/5, 2/5 (4 fractions). Count=4 > 3, High=0.5. Mid=0.25. Count <= 0.25: 1/5 (1 fraction). Count=1 < 3, Low=0.25. Converges to a value where count=3 and max fraction seen is 2/5.

java
public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double low = 0, high = 1.0;
        int[] res = new int[2];
        
        while (high - low > 1e-9) {
            double mid = (low + high) / 2;
            int count = 0;
            double maxF = 0.0;
            int p = 0, q = 0;
            
            for (int i = 0, j = 1; i < arr.length - 1; i++) {
                while (j < arr.length && arr[i] > mid * arr[j]) j++;
                count += arr.length - j;
                if (j < arr.length && (double)arr[i] / arr[j] > maxF) {
                    maxF = (double)arr[i] / arr[j];
                    p = arr[i]; q = arr[j];
                }
            }
            
            if (count == k) return new int[]{p, q};
            if (count > k) high = mid;
            else low = mid;
        }
        return res;
    }
}
Approach 3

Level III: Min-Heap (Sorted Pointers)

Intuition

This problem is similar to 'Merging K Sorted Lists'. For each denominator arr[j], the possible numerators arr[0], arr[1], ..., arr[j-1] create a sorted sequence of fractions. We can use a Min-Heap to store the smallest fraction for each possible denominator arr[j]. We pop the overall smallest and replace it with the next numerator from that same denominator's list.

⏱ O((K + N) log N) where N is the length of arr. We start with N elements in the heap and pop K times.💾 O(N) for the Min-Heap.

Detailed Dry Run

arr = [1, 2, 3, 5], k = 3 Initial Heap: {1/5, 1/3, 1/2}

  1. Pop 1/5. Next num for denom 5 is 2. Heap: {1/3, 1/2, 2/5}. Pop count = 1.
  2. Pop 1/3. Next num for denom 3 is 2. Heap: {1/2, 2/5, 2/3}. Pop count = 2.
  3. Pop 2/5. Pop count = 3. Done. Result [2, 5].
java
import java.util.*;

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        // {numeratorIdx, denominatorIdx}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Double.compare((double)arr[a[0]]/arr[a[1]], (double)arr[b[0]]/arr[b[1]])
        );
        
        for (int j = 1; j < arr.length; j++) {
            minHeap.offer(new int[]{0, j});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] curr = minHeap.poll();
            if (curr[0] + 1 < curr[1]) {
                minHeap.offer(new int[]{curr[0] + 1, curr[1]});
            }
        }
        
        int[] result = minHeap.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}
← Previous QuestionSmallest Range Covering Elements from K Lists
Next Question →Valid Parentheses