What is the time complexity of K-th Smallest Prime Fraction?

The optimal solution has a time complexity of O(n log(1/epsilon)).

What data structures are used to solve K-th Smallest Prime Fraction?

This problem uses Array, Two Pointers, Binary Search, Sorting, Heap (Priority Queue). Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving K-th Smallest Prime Fraction?

Insight 1: Binary search is an effective approach since we're looking for the k-th smallest value within a range of possible fractions (0 to 1). Instead of generating all fractions and sorting them, which would be O(n^2 log n), we can use binary search to find the k-th smallest fraction by repeatedly guessing a value and counting how many fractions are smaller than our guess. Insight 2: A crucial optimization is to avoid explicitly calculating all fractions. Instead, for a given 'mid' value in our binary search, we can efficiently count the number of fractions `arr[i] / arr[j]` that are less than 'mid' in O(n) time using a two-pointer approach.

Which companies ask LeetCode 786. K-th Smallest Prime Fraction in interviews?

This problem is frequently asked at Pony.ai.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

K-th Smallest Prime Fraction - LeetCode 786 Solution

Q: How to solve K-th Smallest Prime Fraction?

The solution employs a binary search algorithm to find the k-th smallest fraction. The binary search operates on the possible range of fraction values, which is between 0 and 1. In each iteration, the algorithm calculates a 'mid' value and counts the number of fractions in the array that are less than this 'mid' value. The count is determined using a two-pointer approach. If the count is less than k, the lower bound of the search space is adjusted to 'mid'; otherwise, the upper bound is adjusted to 'mid'. This process continues until the difference between the upper and lower bounds is sufficiently small (less than 1e-9). The numerator and denominator of the fraction closest to the final 'mid' value are then returned.

K-th Smallest Prime Fraction - Complete Solution Guide

K-th Smallest Prime Fraction is LeetCode problem 786, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 k th 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 so

Detailed Explanation

The problem asks us to find the k-th smallest fraction formed by pairs of elements in a sorted array `arr` containing 1 and prime numbers. Each fraction is of the form `arr[i] / arr[j]` where `0 <= i < j < arr.length`. The task is to return the pair `[arr[i], arr[j]]` that represents the k-th smallest fraction when all possible fractions are sorted in ascending order. The input is a sorted array of integers `arr` and an integer `k`. The output is an array of two integers representing the numerator and denominator of the k-th smallest fraction.

Solution Approach

The solution employs a binary search algorithm to find the k-th smallest fraction. The binary search operates on the possible range of fraction values, which is between 0 and 1. In each iteration, the algorithm calculates a 'mid' value and counts the number of fractions in the array that are less than this 'mid' value. The count is determined using a two-pointer approach. If the count is less than k, the lower bound of the search space is adjusted to 'mid'; otherwise, the upper bound is adjusted to 'mid'. This process continues until the difference between the upper and lower bounds is sufficiently small (less than 1e-9). The numerator and denominator of the fraction closest to the final 'mid' value are then returned.

Step-by-Step Algorithm

Step 1: Initialize `low` to 0.0 and `high` to 1.0, representing the lower and upper bounds of possible fraction values.
Step 2: Initialize `result_p` and `result_q` to 0 and 1, respectively. These will store the numerator and denominator of the closest fraction found so far.
Step 3: Perform a binary search while `high - low > 1e-9`.
Step 4: Calculate `mid = low + (high - low) / 2`.
Step 5: Initialize `count` to 0, `p` to 0, and `q` to 1. `count` will store the number of fractions smaller than `mid`, and `p/q` will store the largest fraction smaller than `mid` found so far.
Step 6: Use a two-pointer approach to count the fractions smaller than `mid`. Iterate through the array using `i` from 0 to `n - 2`. For each `i`, find the largest `j` such that `arr[i] / arr[j] < mid` or `arr[i] < mid * arr[j]`. The number of fractions `arr[i] / arr[j]` smaller than `mid` is then `n - j`.
Step 7: Inside the inner loop, if `arr[i] / arr[j]` is greater than the current `p/q`, update `p` and `q` to `arr[i]` and `arr[j]`, respectively.
Step 8: If `count < k`, update `low = mid`. This means that the 'mid' value is too small, and we need to search in the upper half of the range.
Step 9: Otherwise, update `result_p = p`, `result_q = q`, and `high = mid`. This means that the 'mid' value is too large, and we need to search in the lower half of the range. Also update the best known fraction.
Step 10: After the binary search completes, return `[result_p, result_q]`.

Key Insights

Insight 1: Binary search is an effective approach since we're looking for the k-th smallest value within a range of possible fractions (0 to 1). Instead of generating all fractions and sorting them, which would be O(n^2 log n), we can use binary search to find the k-th smallest fraction by repeatedly guessing a value and counting how many fractions are smaller than our guess.
Insight 2: A crucial optimization is to avoid explicitly calculating all fractions. Instead, for a given 'mid' value in our binary search, we can efficiently count the number of fractions `arr[i] / arr[j]` that are less than 'mid' in O(n) time using a two-pointer approach.
Insight 3: The problem constraints guarantee the existence of the k-th smallest fraction, and the sorted nature of the input array is crucial for the efficiency of the two-pointer technique within the binary search.

Complexity Analysis

Time Complexity: O(n log(1/epsilon))

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Binary Search, Sorting, Heap (Priority Queue).

Companies

Asked at: Pony.ai.

K-th Smallest Prime Fraction | LeetCode 786

Medium

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

Time: O(n log(1/epsilon))Space: O(1)

Solution Code

Available in:

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        double low = 0.0;
        double high = 1.0;
        
        int result_p = 0, result_q = 1;

        while (high - low > 1e-9) {
            double mid = low + (high - low) / 2;
            
            int count = 0;
            int p = 0, q = 1;
            
            int j = 1;
            for (int i = 0; i < n - 1; i++) {
                while (j < n && arr[i] > mid * arr[j]) {
                    j++;
                }
                
                if (j == n) {
                    break;
                }
                
                count += (n - j);
                
                if ((double)arr[i] * q > (double)p * arr[j]) {
                    p = arr[i];
                    q = arr[j];
                }
            }

            if (count < k) {
                low = mid;
            } else {
                result_p = p;
                result_q = q;
                high = mid;
            }
                
        }
        return new int[]{result_p, result_q};
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 786: K-th Smallest Prime Fraction - Detailed explanation and solution approaches.

Topics

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

Companies

Pony.ai

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:786

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize `low` to 0.0 and `high` to 1.0, representing the lower and upper bounds of possible fraction values.
2
Step 2: Initialize `result_p` and `result_q` to 0 and 1, respectively. These will store the numerator and denominator of the closest fraction found so far.
3
Step 3: Perform a binary search while `high - low > 1e-9`.
4
Step 4: Calculate `mid = low + (high - low) / 2`.
5
Step 5: Initialize `count` to 0, `p` to 0, and `q` to 1. `count` will store the number of fractions smaller than `mid`, and `p/q` will store the largest fraction smaller than `mid` found so far.
6
Step 6: Use a two-pointer approach to count the fractions smaller than `mid`. Iterate through the array using `i` from 0 to `n - 2`. For each `i`, find the largest `j` such that `arr[i] / arr[j] < mid` or `arr[i] < mid * arr[j]`. The number of fractions `arr[i] / arr[j]` smaller than `mid` is then `n - j`.
7
Step 7: Inside the inner loop, if `arr[i] / arr[j]` is greater than the current `p/q`, update `p` and `q` to `arr[i]` and `arr[j]`, respectively.
8
Step 8: If `count < k`, update `low = mid`. This means that the 'mid' value is too small, and we need to search in the upper half of the range.
9
Step 9: Otherwise, update `result_p = p`, `result_q = q`, and `high = mid`. This means that the 'mid' value is too large, and we need to search in the lower half of the range. Also update the best known fraction.
10
Step 10: After the binary search completes, return `[result_p, result_q]`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log(1/epsilon))

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity stems from the binary search (logarithmic) multiplied by the linear time required for the fraction counting step. Space complexity is constant as the algorithm utilizes a fixed number of variables irrespective of the input array's size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Heap (Priority Queue)

Create a min-heap of fractions. Initially, the heap contains fractions `arr[0]/arr[i]` for all `i > 0`. In each step, extract the smallest fraction from the heap and insert a new fraction into the heap (if possible). Repeat this k times to get the k-th smallest fraction.

Time: O(k log n)Space: O(n)

Trade-offs: This approach is more efficient when `k` is significantly smaller than `n^2`. However, if `k` is close to `n^2`, the binary search approach is generally faster. The heap approach also requires extra space for the heap.

Sorting All Fractions

Generate all n*(n-1)/2 fractions, store them in a list of pairs (numerator, denominator), sort the list based on the fraction values, and then return the k-th element.

Time: O(n^2 log n)Space: O(n^2)

Trade-offs: This approach is simple to understand and implement but has a higher time and space complexity, making it less efficient than the binary search or heap approaches, especially for large input arrays. Avoid this method when possible.

✨

Key Insights

1Insight 1: Binary search is an effective approach since we're looking for the k-th smallest value within a range of possible fractions (0 to 1). Instead of generating all fractions and sorting them, which would be O(n^2 log n), we can use binary search to find the k-th smallest fraction by repeatedly guessing a value and counting how many fractions are smaller than our guess.
2Insight 2: A crucial optimization is to avoid explicitly calculating all fractions. Instead, for a given 'mid' value in our binary search, we can efficiently count the number of fractions `arr[i] / arr[j]` that are less than 'mid' in O(n) time using a two-pointer approach.
3Insight 3: The problem constraints guarantee the existence of the k-th smallest fraction, and the sorted nature of the input array is crucial for the efficiency of the two-pointer technique within the binary search.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: `arr = [1, 2], k = 1`. The algorithm correctly identifies 1/2 as the smallest fraction.
Edge case 2: `k` is close to `arr.length * (arr.length - 1) / 2`. The binary search handles this case efficiently without needing to generate and sort all fractions.
Edge case 3: The input array only has two elements. The algorithm can still perform the calculations correctly due to the binary search and two-pointer logic designed to work with at least two numbers.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to use binary search and trying to generate and sort all fractions, leading to a time complexity of O(n^2 log n).

✗Common mistake 2: Incorrectly implementing the two-pointer approach, resulting in an incorrect count of fractions smaller than 'mid'. Care must be taken to update `j` correctly.

✗Common mistake 3: Not setting the precision of the binary search high enough (e.g., not using 1e-9 or a similar small value), which can lead to incorrect results.

✗Common mistake 4: Integer overflow when comparing fractions (arr[i] * q > p * arr[j]), should use double type conversion for comparison.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Finding the k-th percentile of ratios in financial data, such as price-to-earnings ratios of companies.

🏦Real-world scenario 2: Determining the k-th smallest ratio of resource consumption in a system with various resource allocations, helpful in resource optimization and fair allocation.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 6, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "K-th Smallest Prime Fraction"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?