K-th Smallest Prime Fraction

class Solution {
public:
    vector<int> findKthSmallestFraction(vector<int>& nums, int k) {
        priority_queue<pair<double, pair<int, int>>> maxHeap;

        for (int i = 0; i < nums.size() - 1; i++)
            maxHeap.push({-1.0 * nums[i] / nums.back(), {i, nums.size() - 1}});
        
        while (--k > 0) {
            pair<int, int> idxPair = maxHeap.top().second;
            maxHeap.pop();
            idxPair.second--;
            maxHeap.push({-1.0 * nums[idxPair.first] / nums[idxPair.second], 
                    {idxPair.first, idxPair.second}});
        }
        
        pair<int, int> finalPair = maxHeap.top().second;
        return {nums[finalPair.first], nums[finalPair.second]};
    }
};

The given C++ solution focuses on finding the k-th smallest prime fraction from a given list of sorted prime numbers. It employs a max heap approach to keep track of the smallest fractions during its iteration over the list.

Here is a summary of how the solution operates:

• Initialize a max heap to store each fraction in the order of their values with their respective indices.

• Iterate through the array of numbers. For each number, consider the fraction formed by the current number and the last number in the array, then push its negative value (to mimic a min-heap using max-heap) and indices into the heap.

• The main loop continues until k decrements to 0. In each loop iteration, the pair (index pair of numerator and denominator which represents the smallest fraction currently) is acquired from the top of the heap. The heap then pops the top element and pushes a new fraction formed by decreasing the index of the denominator.

• This process continues until the k-th smallest fraction is found. When k is 1, the loop ends, and the fraction at the top of the heap is determined as the k-th smallest.

• Finally, a vector is returned containing the numerator and denominator of the k-th smallest fraction based on the indices stored in the heap.

This efficient use of a priority queue (max heap) to simulate the operations of a min heap by storing negative values ensures that the algorithm efficiently finds the k-th smallest fraction with a reduced computational complexity compared to a more naive approach.

class Solution {
    public int[] findKthSmallestFraction(int[] primes, int k) {
        PriorityQueue<double[]> queue = new PriorityQueue<>((x, y) -> Double.compare(y[0], x[0]));
        
        for (int i = 0; i < primes.length - 1; i++) {
            queue.add(new double[] {
                -1.0 * primes[i] / primes[primes.length - 1], 
                i, 
                primes.length - 1
            });
        }
        
        for (int j = 1; j < k; j++) {
            double[] current = queue.poll();
            int numIndex = (int) current[1];
            int denomIndex = (int) current[2] - 1;
            if (denomIndex > numIndex) {
                queue.add(new double[] {
                    -1.0 * primes[numIndex] / primes[denomIndex], 
                    numIndex, 
                    denomIndex
                });
            }
        }
        
        double[] smallest = queue.poll();
        return new int[] {primes[(int) smallest[1]], primes[(int) smallest[2]]};
    }
}

This Java solution aims to find the k-th smallest prime fraction from a given array of prime numbers using a priority queue. Here’s a concise approach to understand the solution:

• Initialize a PriorityQueue to store fractions as negative doubles alongside their indices, ensuring the smallest fractions have higher priority (effectively turning the max-heap into a min-heap by storing fractions negatively).

• Populate the queue with the initial set of fractions formed by dividing elements of the array by the last element in the array. This setup starts the process to determine the smallest fractions.

• Loop through the number of times equal to (k - 1), extracting the smallest fraction each time and generating a new fraction by decreasing the denominator's index, subsequently adding it back to the queue if it remains valid.

• After iterating k-1 times, the top of the queue will hold the k-th smallest prime fraction. Convert the indices back to corresponding prime numbers before returning the result.

Each step efficiently narrows down to finding the k-th smallest fraction without the need to sort all potential fractions, utilizing priority queues for optimizing retrieval and insertion operations.

class Solution:
    def findKthSmallestFraction(self, nums, position):
        import heapq
        # Min-heap to manage smallest fractions
        min_heap = []

        # Insert fractions of nums[i] by the final element
        for index in range(len(nums) - 1):
            heapq.heappush(min_heap, (nums[index] / nums[-1], index, len(nums) - 1))

        # Pop smallest elements until we reach the k-th one
        for _ in range(position - 1):
            smallest = heapq.heappop(min_heap)
            num_idx = smallest[1]
            den_idx = smallest[2] - 1
            if den_idx > num_idx:
                heapq.heappush(min_heap, (nums[num_idx] / nums[den_idx], num_idx, den_idx))

        # The top element is the k-th smallest
        smallest_fraction = heapq.heappop(min_heap)
        return [nums[smallest_fraction[1]], nums[smallest_fraction[2]]]

This solution tackles the problem of finding the K-th smallest prime fraction from a sorted list of integers. The implementation unfolds in Python using a min-heap to efficiently track and sort the fractions.

• Start by importing the heapq library to create a min-heap structure.
• Initialize a min-heap to store the fractions composed of the integer pairs from the list.
• Populate the heap: for each number in the list (excluding the last), calculate the fraction of this number over the last number in the list, then push this fraction along with the indices of the numerator and denominator into the heap.
• Remove fractions from the heap one at a time until reaching the K-th smallest fraction.
• If the denominator index indicates that a smaller denominator can be used (while remaining larger than the numerator index), push the new fraction produced with this smaller denominator onto the heap.
• Finally, retrieve and return the top element from the heap once you've removed the desired number of prior elements. This element represents the K-th smallest fraction and its indices correspond to the desired numerator and denominator in the original list.

Consider efficient memory usage and accurate indexing throughout this process to ensure optimal performance and correctness. This approach ensures that the time complexity is manageable by reducing the pool of potential fractions using the heap's ordering properties.