Scale Engineer

K-th Smallest Prime Fraction

Med
#0740Time: 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.1 company
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
ArrayHeap (Priority Queue)
Companies
Pony.ai

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

Solutions

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;    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem