algoadvance

Leetcode 786. K

Problem Statement

Given a sorted array of integers arr containing 1 and prime numbers, you need to find the k-th smallest fraction in the form arr[i]/arr[j] where 0 <= i < j < arr.length. Return the fraction in the form of an array of two integers [arr[i], arr[j]].

Clarifying Questions

  1. Range of values in arr: What are the possible values or size ranges for arr?
    • Generally, the size can be from 1 to 1000 and values can range from 1 to 10⁻⁴.
  2. Value of k: Is k always valid, i.e., does k always fall within the range of possible fractions?
    • Yes, the value for k will always be valid as per the constraints.
  3. Duplicates: Can arr contain duplicate numbers?
    • According to the problem, arr contains only 1 and distinct prime numbers.
  4. Output Format: Should the fractions be returned in any specific form?
    • Yes, return the fractions in the form of an array [arr[i], arr[j]].

Strategy

  1. Heap Approach:
    • Use a min-heap (priority queue) to keep track of the k-th smallest fractions.
    • Since the array is already sorted in ascending order, the smallest fractions will be those involving smaller indices initially.
  2. Binary Search Approach:
    • Binary search can be used to find the k-th smallest fraction by searching over possible values between the smallest (arr[0]/arr[arr.length-1]) and the largest fraction (arr[arr.length-2]/arr[arr.length-1]).
    • The process involves checking the number of fractions that are less than or equal to the middle fraction (in terms of value).

Chosen Approach: Binary Search (due to better efficiency)

  1. Initialize Left (low) and Right (high): Initialize the search range for fractions.
  2. Counting Fractions Less Than Mid: Create a helper function to count and possibly track the fractions less than a given value.
  3. Binary Search Loop: Adjust low and high based on the count.
  4. Find Exact Fraction: Keep searching fractions within these bounds until the k-th fraction is found.

Code

import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double low = 0.0, high = 1.0;
        
        while (low < high) {
            double mid = (low + high) / 2.0;
            int[] result = countFractions(arr, mid);
            
            if (result[2] < k) {
                low = mid;
            } else {
                high = mid;
            }
            
            if (Math.abs(low - high) < 1e-9) {
                return new int[] {arr[result[0]], arr[result[1]]};
            }
        }
        
        return new int[] {};  // Should never be reached.
    }

    private int[] countFractions(int[] arr, double mid) {
        int count = 0;
        int n = arr.length;
        int x = 0, y = n - 1;
        
        int best_i = 0, best_j = 0;
        double best_fraction = 0.0;
        
        for (int i = 0; i < n; i++) {
            while (y >= 0 && (double) arr[i] / arr[y] > mid) {
                y--;
            }
            if (y >= 0) {
                count += y + 1;
                if ((double) arr[i] / arr[y] > best_fraction) {
                    best_i = i;
                    best_j = y;
                    best_fraction = (double) arr[i] / arr[y];
                }
            }
        }
        
        return new int[] {best_i, best_j, count};
    }
}

Time Complexity

This solution efficiently finds the k-th smallest prime fraction using a combination of binary search and counting methodology.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI