786. K-th Smallest Prime Fraction • Algorithm Solutions

1. Description

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

2. Example

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]

3. Constraints

2 <= arr.length <= 1000
1 <= arr[i] <= $3 * 10^4$
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

4. Solutions

Heap(Priority Queue)

n = arr.size()
Time complexity: O(klogn)
Space complexity: O(n)

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(const vector<int> &arr, int k) {
        auto greater = [&](const pair<int, int> &x, const pair<int, int> &y) {
            return arr[x.first] * arr[y.second] > arr[y.first] * arr[x.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(greater)> fraction_queue(
            greater);
        // since all the numbers of arr are unique and sorted in strictly increasing order
        // for the fraction i/j, arr[i]/arr[j] always < arr[i+1]/arr[j]
        // we maintain a queue to include every denominator j, and find min value every time
        // until to find kth value
        for (int i = 1; i < arr.size(); ++i) {
            fraction_queue.emplace(0, i);
        }

        for (int i = 1; i < k; ++i) {
            auto [numerator, denominator] = fraction_queue.top();
            fraction_queue.pop();

            if (numerator + 1 < denominator) {
                fraction_queue.emplace(numerator + 1, denominator);
            }
        }

        return {arr[fraction_queue.top().first], arr[fraction_queue.top().second]};
    }
};

Binary Search

n = arr.size(), C is upper bound of search times
Time complexity: O(nlogC)
Space complexity: O(1)

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(const vector<int> &arr, int k) {
        // 1 <= arr[i] <= 3 * 10^4
        // so min value is 1 / 3 * 10^4
        // and min diff is (1 / 3 * 10^4 - 1) - (1 / 3 * 10^4)
        // it is about 1 / 9 * 10^8, which needs 30 times binary search(30 times / 2)
        for (double left = 0.0, right = 1.0; left < right;) {
            double mid = (left + right) / 2;

            int x = 0, y = 1, count = 0; // x/y is used to record the max number
            for (int i = 0, j = 1; j < arr.size(); ++j) {
                while ((double)arr[i] / arr[j] < mid) {
                    if (arr[i] * y > arr[j] * x) { // find the max number
                        x = arr[i];
                        y = arr[j];
                    }
                    ++i;
                }
                count += i;
                // i is an index, but it is the first invalid index
                // when we need an count, we use (i + 1), so the count is (i - 1 + 1), i.e., i
            }

            if (count == k) {
                return {x, y};
            }

            count < k ? left = mid : right = mid;
        }

        return {};
    }
};