Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go

• 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();
      }
  }
  

• // OJ: https://leetcode.com/problems/k-th-smallest-prime-fraction/
  // Time: O(KlogN)
  // Space: O(N)
  class Solution {
      typedef array<int, 2> T;
  public:
      vector<int> kthSmallestPrimeFraction(vector<int>& A, int k) {
          auto cmp = [&](T &a, T &b) { return (double)A[a[0]] / A[a[1]] > (double)A[b[0]] / A[b[1]]; };
          priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);
          for (int i = 0; i < A.size() - 1; ++i) pq.push({ i, (int)A.size() - 1 });
          while (--k) {
              auto [a, b]  = pq.top();
              pq.pop();
              if (a != b - 1) pq.push({ a, b - 1 });
          }
          auto [a, b] = pq.top();
          return { A[a], A[b] };
      }
  };
  

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

• type frac struct{ x, y, i, j int }
  type hp []frac
  
  func (a hp) Len() int            { return len(a) }
  func (a hp) Swap(i, j int)       { a[i], a[j] = a[j], a[i] }
  func (a hp) Less(i, j int) bool  { return a[i].x*a[j].y < a[j].x*a[i].y }
  func (a *hp) Push(x interface{}) { *a = append(*a, x.(frac)) }
  func (a *hp) Pop() interface{}   { l := len(*a); tmp := (*a)[l-1]; *a = (*a)[:l-1]; return tmp }
  
  func kthSmallestPrimeFraction(arr []int, k int) []int {
  	n := len(arr)
  	h := make(hp, 0, n-1)
  	for i := 1; i < n; i++ {
  		h = append(h, frac{1, arr[i], 0, i})
  	}
  	heap.Init(&h)
  	for i := 1; i < k; i++ {
  		f := heap.Pop(&h).(frac)
  		if f.i+1 < f.j {
  			heap.Push(&h, frac{arr[f.i+1], arr[f.j], f.i + 1, f.j})
  		}
  	}
  	return []int{h[0].x, h[0].y}
  }
  
  

All Problems

All Solutions