← Back to Index

📚 K-th Smallest Prime Fraction – Java Cheat Sheet

📌 What Is It?

The problem involves finding the K-th smallest fraction formed by two elements from a sorted array of prime numbers. Each fraction is of the form A[i] / A[j] where i < j.

This problem can be efficiently solved using a min-heap to track the smallest fractions.

🧱 Pattern Template

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> 
            arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);

        // Step 1: Add the first fraction from each element in arr with the last element
        for (int i = 0; i < arr.length - 1; i++) {
            minHeap.offer(new int[]{i, arr.length - 1}); // [numeratorIndex, denominatorIndex]
        }

        // Step 2: Extract the smallest fractions from the heap
        while (--k > 0) {
            int[] smallest = minHeap.poll();
            int i = smallest[0];
            int j = smallest[1];

            // Add the next fraction with the same numerator but a smaller denominator
            if (j - 1 > i) {
                minHeap.offer(new int[]{i, j - 1});
            }
        }

        int[] result = minHeap.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

📊 Time Complexity

• Heap Initialization: O(n log n) – Adding the first fractions to the heap.
• Heap Operations: O(k log n) – Extracting and adding elements to the heap for k fractions.
• Overall Complexity: O(k log n).

✅ Use Cases

• Finding the smallest or largest fractions in a sorted array
• Efficiently combining sorted data streams
• Applications in optimization and scheduling problems

📘 Common LeetCode Problems

• 786. K-th Smallest Prime Fraction [Hard] Heap

🧪 Example: K-th Smallest Prime Fraction

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

Explanation:
- The fractions are [1/5, 1/3, 1/2, 2/5, 3/5].
- The 3rd smallest fraction is 2/5.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest fractions.
• Edge cases: empty arrays, k greater than the total number of fractions.
• Ensure the heap stores enough information to track the indices of the numerator and denominator.