Formatted question description: https://leetcode.ca/all/786.html

786. K-th Smallest Prime Fraction

Level

Hard

Description

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:

Input: A = [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, 2/3. The third fraction is 2/5.

Input: A = [1, 7], K = 1

Output: [1, 7]

Note:

• A will have length between 2 and 2000.
• Each A[i] will be between 1 and 30000.
• K will be between 1 and A.length * (A.length - 1) / 2.

Solution

Use a priority queue to store the fractions, where the smallest fraction is polled first. Initially, offer all [A[0], A[i]] where 0 < i < A.length to the priority queue. Since A[0] is 1 and the smallest fraction has a numerator 1, the smallest fraction is in the priority queue.

Then poll the smallest fraction from the priority queue for K - 1 times. To ensure that the remaining smallest fraction is in the priority queue, each time a fraction is polled, try to find the next smallest fraction and offer it to the priority queue if it exists. Suppose the fraction polled is [A[i], A[j]] where 0 <= i < j < A.length. If i + 1 < j, then offer the new fraction [A[i + 1], A[j]] to the priority queue.

After the K - 1 times, the next element to be polled from the priority queue is the K-th smallest prime fraction, so return the fraction.

class Solution {
    public int[] kthSmallestPrimeFraction(int[] A, int K) {
        Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
        int length = A.length;
        for (int i = 0; i < length; i++)
            numIndexMap.put(A[i], i);
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] fraction1, int[] fraction2) {
                return fraction1[0] * fraction2[1] - fraction2[0] * fraction1[1];
            }
        });
        for (int i = 1; i < length; i++) {
            int[] fraction = {A[0], A[i]};
            priorityQueue.add(fraction);
        }
        for (int i = 1; i < K; i++) {
            int[] fraction = priorityQueue.poll();
            int numeratorIndex = numIndexMap.get(fraction[0]), denominatorIndex = numIndexMap.get(fraction[1]);
            if (numeratorIndex + 1 < denominatorIndex) {
                numeratorIndex++;
                int[] newFraction = {A[numeratorIndex], fraction[1]};
                priorityQueue.offer(newFraction);
            }
        }
        return priorityQueue.peek();
    }
}

All Problems

All Solutions