# K-th Smallest Prime Fraction
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-th-smallest-prime-fraction)
Canonical: https://scaleengineer.com/dsa/problems/k-th-smallest-prime-fraction
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Pony.ai](https://scaleengineer.com/companies/pony.ai)
---
## Problem
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]`.

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

**Constraints:**

* `2 <= arr.length <= 1000`
* `1 <= arr[i] <= 3 * 104`
* `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`

**Follow up:** Can you solve the problem with better than `O(n2)` complexity?

# Approaches
## Brute Force with Sorting
This approach is the most straightforward and intuitive. The idea is to first generate every possible fraction `arr[i] / arr[j]` for `i < j`. These fractions are then stored in a list. After generating all fractions, the list is sorted in ascending order. Finally, the k-th element (at index `k-1`) of the sorted list is the desired answer.
**Time:** O(N^2 log N). Generating the `O(N^2)` fractions takes `O(N^2)` time. Sorting this list of `O(N^2)` elements takes `O(N^2 log(N^2))`, which simplifies to `O(N^2 log N)`. · **Space:** O(N^2), where N is the length of `arr`. This is because we need to store all `N * (N - 1) / 2` possible fractions in a list.
**Pros:** Simple to understand and implement.; Guaranteed to be correct if implemented properly.
**Cons:** High time complexity, making it potentially too slow for large inputs.; High space complexity, as it requires storing all possible fractions.
### Explanation
The implementation involves two nested loops to iterate through all pairs of indices `(i, j)` such that `0 <= i < j < arr.length`. For each pair, we form a fraction `[arr[i], arr[j]]` and add it to a list. Once all fractions are collected, we use a custom comparator to sort them. The comparison `a/b < c/d` is equivalent to `a*d < c*b`, which avoids using floating-point arithmetic and its associated precision problems. After sorting, the fraction at index `k-1` is the result.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        List<int[]> fractions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                fractions.add(new int[]{arr[i], arr[j]});
            }
        }

        // Sort the fractions using a custom comparator
        Collections.sort(fractions, (a, b) -> {
            // Compare a[0]/a[1] and b[0]/b[1]
            // This is equivalent to comparing a[0]*b[1] and b[0]*a[1]
            return Integer.compare(a[0] * b[1], b[0] * a[1]);
        });

        return fractions.get(k - 1);
    }
}
```
### Algorithm
*   Create a list to store fractions. Each fraction can be represented as a pair of integers `[numerator, denominator]`.
*   Iterate through the input array `arr` with two nested loops to generate all possible fractions `arr[i] / arr[j]` where `i < j`.
*   For each valid pair `(i, j)`, add the fraction `[arr[i], arr[j]]` to the list.
*   After generating all `N * (N - 1) / 2` fractions, sort the list. The comparison between two fractions `a/b` and `c/d` is performed using cross-multiplication (`a*d` vs `c*b`) to avoid floating-point precision issues.
*   The k-th smallest fraction is located at index `k-1` in the sorted list. Return this fraction.

## Using a Min-Heap (Priority Queue)
This approach improves upon the brute-force method by avoiding the generation and storage of all fractions at once. We can think of the fractions as being organized into `N-1` sorted lists, where each list corresponds to a fixed denominator `arr[j]` and contains fractions `arr[0]/arr[j], arr[1]/arr[j], ...`. The problem then becomes finding the k-th smallest element from these `N-1` sorted lists. A min-heap is a perfect data structure for this task.
**Time:** O((N + K) log N). Initializing the heap takes `O(N log N)`. Each of the `K` extractions and subsequent insertions takes `O(log N)`. If `K` is small, this is efficient. If `K` is `O(N^2)`, the complexity approaches `O(N^2 log N)`. · **Space:** O(N), where N is the length of `arr`. The heap stores at most `N-1` elements.
**Pros:** Significant improvement in space complexity over the brute-force approach.; Generally faster than brute-force, especially for smaller values of `k`.
**Cons:** The time complexity can be slow if `k` is large, approaching `O(N^2)`.
### Explanation
We use a min-heap to efficiently manage the smallest current element from each of the conceptual sorted lists. The heap will store pairs of indices `[i, j]` corresponding to the fraction `arr[i]/arr[j]`. The comparison logic for the heap will be based on the fraction's value, using cross-multiplication to maintain precision.

Initially, we populate the heap with the first (and smallest) element from each of the `N-1` lists: `arr[0]/arr[1]`, `arr[0]/arr[2]`, ..., `arr[0]/arr[N-1]`. Then, we repeatedly extract the minimum fraction from the heap. After extracting a fraction `arr[i]/arr[j]`, we add the next fraction from the same list, `arr[i+1]/arr[j]`, to the heap (if it exists). We repeat this process `k` times. The `k`-th fraction extracted is our answer.

```java
import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        // Min-heap stores {numerator_index, denominator_index}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> 
            Integer.compare(arr[a[0]] * arr[b[1]], arr[b[0]] * arr[a[1]]));

        // Initially, push the smallest fraction from each 'column' (denominator)
        // The smallest fraction for denominator arr[j] is arr[0]/arr[j]
        for (int j = 1; j < n; j++) {
            pq.offer(new int[]{0, j});
        }

        // Extract the smallest element k-1 times
        for (int count = 0; count < k - 1; count++) {
            int[] top = pq.poll();
            int i = top[0];
            int j = top[1];

            // If there's a next element in the same column, add it to the heap
            if (i + 1 < j) {
                pq.offer(new int[]{i + 1, j});
            }
        }

        // The top of the heap is now the k-th smallest fraction
        int[] resultIndices = pq.poll();
        return new int[]{arr[resultIndices[0]], arr[resultIndices[1]]};
    }
}
```
### Algorithm
*   Create a min-heap (Priority Queue) that stores pairs of indices `[i, j]`, representing the fraction `arr[i]/arr[j]`. The heap is ordered by the value of these fractions.
*   Initialize the heap by adding the smallest fraction for each possible denominator. For each denominator `arr[j]` (where `j` goes from 1 to `N-1`), the smallest fraction is `arr[0]/arr[j]`. So, push the index pairs `[0, j]` for `j = 1, ..., N-1` into the heap.
*   Extract the minimum element from the heap `k` times.
*   For each extracted element `[i, j]`, if there is a next larger fraction with the same denominator `arr[j]` (i.e., `arr[i+1]/arr[j]`), add its index pair `[i+1, j]` to the heap.
*   The `k`-th element extracted from the heap corresponds to the k-th smallest fraction. Return `[arr[i], arr[j]]` for this element.

## Binary Search on the Answer
This is the most optimal approach, leveraging the fact that we are looking for a k-th ordered element. Instead of generating fractions, we can binary search for the *value* of the k-th fraction. The values of all fractions are in the range `[0, 1]`. For any guessed value `x` in this range, we can efficiently determine how many fractions are smaller than or equal to `x`. This information allows us to narrow down the search range for the value, similar to a standard binary search on a sorted array.
**Time:** O(N log W), where N is the length of the array and W is the range of values. The `log W` factor represents the number of binary search iterations, which is effectively constant due to the required precision (e.g., `log(10^9)` is about 30). The counting step inside the loop takes `O(N)`. Therefore, the overall time complexity is effectively linear, `O(N)`. · **Space:** O(1). The algorithm only requires a few variables to maintain the state of the binary search and the two-pointer count, regardless of the input size.
**Pros:** Extremely efficient time complexity.; Optimal space complexity.
**Cons:** More complex to conceptualize and implement correctly.; Requires careful handling of floating-point numbers and the binary search termination condition.
### Explanation
We define a search space for the fraction's value, `[low, high]`, initialized to `[0.0, 1.0]`. In each step of the binary search, we pick a `mid` value. We then need to count how many pairs `(i, j)` with `i < j` satisfy `arr[i] / arr[j] <= mid`. This is equivalent to `arr[i] <= mid * arr[j]`.

This counting can be done in `O(N)` time. We iterate through `j` from 1 to `N-1`. For each `j`, we find the count of `i < j` that satisfy the condition. Since `arr` is sorted, as `j` increases, the upper bound for `arr[i]` (`mid * arr[j]`) also increases. This monotonicity allows us to use a second pointer for `i` that only moves forward, leading to an overall linear time complexity for the count.

During the counting process for a given `mid`, we also track the maximum fraction found that is less than or equal to `mid`. If the total count is less than `k`, we know our `mid` is too small and we must search for a larger value (`low = mid`). If the count is `k` or more, `mid` is a candidate for our answer's value (or is too large), so we record the maximum fraction we found as a potential answer and try to find a better (smaller) value (`high = mid`).

```java
class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        double low = 0.0, high = 1.0;
        int[] ans = new int[2];

        while (high - low > 1e-9) {
            double mid = low + (high - low) / 2.0;
            int count = 0;
            int p = 0, q = 1; // To store the max fraction <= mid

            int i = 0;
            for (int j = 1; j < n; j++) {
                while (i < j && arr[i] < mid * arr[j]) {
                    i++;
                }
                count += i;
                if (i > 0 && arr[i - 1] * q > p * arr[j]) {
                    p = arr[i - 1];
                    q = arr[j];
                }
            }

            if (count < k) {
                low = mid;
            } else {
                ans[0] = p;
                ans[1] = q;
                high = mid;
            }
        }
        return ans;
    }
}
```
### Algorithm
*   The values of the fractions `arr[i]/arr[j]` are all between 0 and 1. We can binary search for the value of the k-th smallest fraction in this range.
*   For a given `mid` value from the binary search, we need a function to count how many fractions are less than or equal to `mid`. Let's call this `count(mid)`.
*   `count(mid)` can be implemented efficiently in `O(N)` time using a two-pointer technique. We iterate through denominators `arr[j]` and for each, find how many numerators `arr[i]` satisfy `arr[i] <= mid * arr[j]`.
*   While counting, we also keep track of the largest fraction encountered that is still less than or equal to `mid`. Let this be `p/q`.
*   Based on the `count`:
    *   If `count < k`, the target fraction's value is larger than `mid`, so we search in `(mid, high]`.
    *   If `count >= k`, `mid` is a potential answer or too high. The answer is in `[low, mid]`. We store `[p, q]` as our current best answer and continue searching in `[low, mid]` to find an even smaller value.
*   The binary search continues until the range `[low, high]` is sufficiently small, and the stored `[p, q]` will be the k-th smallest fraction.

# Solutions
### Java

```java
class Solution {
public
  int[] kthSmallestPrimeFraction(int[] arr, int k) {
    int n = arr.length;
    Queue<Frac> pq = new PriorityQueue<>();
    for (int i = 1; i < n; i++) {
      pq.offer(new Frac(1, arr[i], 0, i));
    }
    for (int i = 1; i < k; i++) {
      Frac f = pq.poll();
      if (f.i + 1 < f.j) {
        pq.offer(new Frac(arr[f.i + 1], arr[f.j], f.i + 1, f.j));
      }
    }
    Frac f = pq.peek();
    return new int[]{f.x, f.y};
  }
  static class Frac implements Comparable {
    int x, y, i, j;
  public
    Frac(int x, int y, int i, int j) {
      this.x = x;
      this.y = y;
      this.i = i;
      this.j = j;
    }
    @Override public int compareTo(Object o) {
      return x * ((Frac)o).y - ((Frac)o).x * y;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k) {
    using pii = pair<int, int>;
    int n = arr.size();
    auto cmp = [&](const pii &a, const pii &b) {
      return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second];
    };
    priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
    for (int i = 1; i < n; ++i) {
      pq.push({0, i});
    }
    for (int i = 1; i < k; ++i) {
      pii f = pq.top();
      pq.pop();
      if (f.first + 1 < f.second) {
        pq.push({f.first + 1, f.second});
      }
    }
    return {arr[pq.top().first], arr[pq.top().second]};
  }
};

```

### Python

```python
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]: h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])] heapify(h) for _ in range(k - 1): _, i, j = heappop(h) if i + 1 < j: heappush(h, (arr[i + 1] / arr[j], i + 1, j)) return [arr[h[0][1]], arr[h[0][2]]]

```