K-th Smallest Prime Fraction

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

Examples

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]

Solution

Video Explanation

Video solution here: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/RzK18Ez5VCI" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Creating all fractions and use Minheap

Code

Java

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<Frac> minHeap = new PriorityQueue<>((a, b) -> Double.compare(a.frac, b.frac));
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double d = (double) arr[i] / arr[j];
                minHeap.add(new Frac(d, arr[i], arr[j]));
            }
        }

        for (int i = 0; i < k - 1; i++) {
            minHeap.poll();
        }

        Frac ans = minHeap.poll();
        return new int[] { ans.nr, ans.dr };
    }

    class Frac {
        double frac;
        int nr;
        int dr;
        public Frac(double frac, int nr, int dr) {
            this.frac = frac;
            this.nr = nr;
            this.dr = dr;
        }
    }
}

Complexity

• ⏰ Time complexity: O(N^2 logn)
• 🧺 Space complexity: O(n^2)

Method 2 - Using provided sorted array efficiently and minHeap 🏆

The optimized method aims to leverage the point that array is sorted. So, we can find the k-th smallest fraction from all possible pairs in a sorted array without generating all combinations upfront.

Algorithm

1. Initialize minHeap based on the fractional value. We don't have. to double compare. Let nr represents numerator and dr represents denominator, this implies if nr0/dr0 > nr1/dr1 ⇨ nr0*dr1 > nr1 * dr0
2. Push all the smallest possible fraction by pushing all numerator with array's largest value as denominator to the minHeap.
3. Extract the smallest fraction from minHeap, and replace it with the next fraction by using same numerator, but just smaller denominator
   1. Continue this step 3, till we have extracted k elements, and kth' element is our answer

Dry Run

1. We create minHeap
2. We push all pairs as {nrIdx, drIdx} ⇨ numerator and denominator index - We push all numerators from 0 to n-2 and last index n-1 as denominators
3. Now, we poll each pair one by one. We poll out numerator and denominator pair. If the we have reached k, we return current answer
   1. and if we have not reached k, we push new {nrIdex, drIdx - 1} provided nrIdx != (drIdx - 1).

Code

Java

public int[] kthSmallestPrimeFraction(int[] arr, int k) {
	PriorityQueue<int[]> minHeap = new PriorityQueue<>(
			(a, b) -> Integer.compare(arr[a[0]] * arr[b[1]], arr[a[1]] * arr[b[0]]));
	int n = arr.length;
	for (int i = 0; i < n - 1; i++) {
		minHeap.add(new int[] { i, n - 1 });
	}

	for (int i = 0; i < k - 1; i++) {
		int[] frac = minHeap.poll();
		int nrIdx = frac[0];
		int drIdx = frac[1];

		if (drIdx - 1 > nrIdx) {
			minHeap.add(new int[] { nrIdx, drIdx - 1 });
		}
	}

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

Complexity

• ⏰ Time complexity: O(n log n) as it takes O(n) to build minHeap and O(k log n) to pick first k elements from heap.
• 🧺 Space complexity: O(n)