Skip to main content

Heaps

K-th Smallest Prime Fraction Solution In C++/Python/Java/JS

Problem Description

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

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.


Input: arr = [1,7], k = 1
Output: [1,7]

Constraints

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 10^4
  • 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
💡
Try it Yourself First
Given a sorted array of 1 and prime numbers, we generate fractions by dividing one element by another. Our goal is to find the k-th smallest fraction in ascending order and return it as [numerator, denominator]. Efficient approaches like min-heaps or binary search help optimize the search instead of generating all fractions explicitly.

Brute Force Approach

Intuition

Our goal is to efficiently determine the k-th smallest fraction from a sorted array containing 1 and prime numbers. Instead of generating and sorting all possible fractions explicitly, we can leverage binary search to systematically narrow down the search space and count the number of fractions smaller than a given reference fraction.

To achieve this, we consider a search range between 0 and 1, since all possible fractions fall within this interval. Using binary search on fraction values, we repeatedly refine the range by choosing a midpoint and counting how many fractions are smaller than or equal to it. This count helps us determine whether we need to shift our search range higher or lower.

Counting the number of fractions smaller than a given reference fraction can be done efficiently using a two-pointer approach. Since the array is sorted, if a fraction arr[i] / arr[j] is smaller than the reference fraction, then all fractions arr[i] / arr[k] (for k > j) will also be smaller. This allows us to efficiently traverse the array and count fractions in O(n) time without explicitly storing them.

As we explore the fraction space, we also keep track of the largest valid fraction found within our current search range. If the number of fractions smaller than our reference fraction is at least k, we adjust the search range accordingly. Eventually, when our search range converges, the maximum fraction encountered in this process will be the k-th smallest fraction, ensuring an optimized and structured approach without unnecessary sorting or brute-force enumeration.

Approach

Step 1: Initialize Class Variables

  • Store n as the length of the input array arr.
  • Set left = 0 and right = 1.0 to define the initial range for binary search.

Step 2: Perform Binary Search

  • Enter a loop while left < right to iteratively refine the search range.
  • Compute the midpoint mid = (left + right) / 2.
  • Initialize maxFraction to store the largest valid fraction found in the current range.
  • Maintain totalSmallerFractions to count how many fractions are smaller than mid.
  • Track indices numeratorIdx and denominatorIdx for the largest fraction encountered.

Step 3: Count Fractions Smaller Than Mid

  • Initialize j = 1 as the denominator index.
  • Iterate through the array and for each arr[i]:
  • Move j forward until arr[i] / arr[j] is greater than mid, ensuring valid fractions.
  • Increment totalSmallerFractions by the number of valid denominators (n - j).
  • If j reaches the array's end, exit the loop.
  • If arr[i] / arr[j] is the largest encountered fraction, update maxFraction, numeratorIdx, and denominatorIdx.

Step 4: Adjust Search Range Based on Count

  • If totalSmallerFractions == k, return the fraction [arr[numeratorIdx], arr[denominatorIdx]].
  • If totalSmallerFractions > k, move right = mid to focus on smaller fractions.
  • If totalSmallerFractions < k, move left = mid to search for larger fractions.

Step 5: Return Result
If the loop completes without finding the k-th fraction, return an empty array.

Dry Run

Input:

  • arr = [1, 2, 3, 5], k = 3

Goal:

  • Find the k-th smallest fraction formed by dividing two elements from arr.

Step 1: Generate All Possible Fractions

  • Since arr is sorted, we generate all valid fractions arr[i] / arr[j] where i < j:
  • Fraction -> Value
  • 1/5 -> 0.200
  • 1/3 -> 0.333
  • 2/5 -> 0.400
  • 1/2 -> 0.500
  • 3/5 -> 0.600
  • 2/3 -> 0.667
  • Sorted order of fractions: [1/5, 1/3, 2/5, 1/2, 3/5, 2/3]
  • k = 3, so the 3rd smallest fraction is 2/5.

Step 2: Return the k-th Smallest Fraction

  • Numerator: 2
  • Denominator: 5
  • Output: [2, 5]

Final Output: [2, 5]

Code for All Languages
C++ 
// Approach: Binary Search with Two Pointers  
// Language: C++  

#include <iostream>  
#include <vector>  

using namespace std;  

class Solution {  
public:  

    // Step 1: Function to find the k-th smallest prime fraction  
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {  

        // Get the size of the array  
        int n = arr.size();  

        // Define the binary search range for fraction values  
        double left = 0, right = 1.0;  

        // Perform binary search to find the k-th smallest fraction  
        while (left < right) {  

            // Calculate the middle value  
            double mid = (left + right) / 2;  

            // Initialize variables to track the best fraction found  
            double maxFraction = 0.0;  
            int totalSmallerFractions = 0;  
            int numeratorIdx = 0, denominatorIdx = 0;  
            int j = 1;  

            // Step 2: Iterate through the array to find fractions smaller than mid  
            for (int i = 0; i < n - 1; i++) {  

                // Move j to find the first fraction greater than mid  
                while (j < n && arr[i] >= mid * arr[j]) {  
                    j++;  
                }  

                // Count the number of fractions smaller than mid  
                totalSmallerFractions += (n - j);  

                // If j reaches the end, break out of the loop  
                if (j == n) break;  

                // Calculate the current fraction  
                double fraction = static_cast<double>(arr[i]) / arr[j];  

                // Update maxFraction and store the indices if it's the largest found  
                if (fraction > maxFraction) {  
                    numeratorIdx = i;  
                    denominatorIdx = j;  
                    maxFraction = fraction;  
                }  
            }  

            // Step 3: Check if we found exactly k fractions smaller than mid  
            if (totalSmallerFractions == k) {  
                return {arr[numeratorIdx], arr[denominatorIdx]};  
            }  
            
            // If we found more than k, search in the left half  
            else if (totalSmallerFractions > k) {  
                right = mid;  
            }  
            
            // If we found fewer than k, search in the right half  
            else {  
                left = mid;  
            }  
        }  

        // Return an empty vector if k-th fraction is not found  
        return {};  
    }  
};

Java 
// Approach: Binary Search with Two Pointers  
// Language: Java  

import java.util.*;  

class Solution {  

    // Step 1: Function to find the k-th smallest prime fraction  
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {  

        // Get the size of the array  
        int n = arr.length;  

        // Define the binary search range for fraction values  
        double left = 0, right = 1.0;  

        // Perform binary search to find the k-th smallest fraction  
        while (left < right) {  

            // Calculate the middle value  
            double mid = (left + right) / 2;  

            // Initialize variables to track the best fraction found  
            double maxFraction = 0.0;  
            int totalSmallerFractions = 0;  
            int numeratorIdx = 0, denominatorIdx = 0;  
            int j = 1;  

            // Step 2: Iterate through the array to find fractions smaller than mid  
            for (int i = 0; i < n - 1; i++) {  

                // Move j to find the first fraction greater than mid  
                while (j < n && arr[i] >= mid * arr[j]) {  
                    j++;  
                }  

                // Count the number of fractions smaller than mid  
                totalSmallerFractions += (n - j);  

                // If j reaches the end, break out of the loop  
                if (j == n) break;  

                // Calculate the current fraction  
                double fraction = (double) arr[i] / arr[j];  

                // Update maxFraction and store the indices if it's the largest found  
                if (fraction > maxFraction) {  
                    numeratorIdx = i;  
                    denominatorIdx = j;  
                    maxFraction = fraction;  
                }  
            }  

            // Step 3: Check if we found exactly k fractions smaller than mid  
            if (totalSmallerFractions == k) {  
                return new int[]{arr[numeratorIdx], arr[denominatorIdx]};  
            }  
            
            // If we found more than k, search in the left half  
            else if (totalSmallerFractions > k) {  
                right = mid;  
            }  
            
            // If we found fewer than k, search in the right half  
            else {  
                left = mid;  
            }  
        }  

        // Return an empty array if k-th fraction is not found  
        return new int[]{};  
    }  
}

Python 
# Approach: Binary Search with Two Pointers  
# Language: Python  

# Step 1: Define the Solution class  
class Solution(object):  

    def kthSmallestPrimeFraction(self, arr, k):  
        """
        :type arr: List[int]  
        :type k: int  
        :rtype: List[int]  
        """  

        # Get the size of the array  
        n = len(arr)  

        # Define the binary search range for fraction values  
        left, right = 0.0, 1.0  

        # Perform binary search to find the k-th smallest fraction  
        while left < right:  

            # Calculate the middle value  
            mid = (left + right) / 2  

            # Initialize variables to track the best fraction found  
            maxFraction = 0.0  
            totalSmallerFractions = 0  
            numeratorIdx, denominatorIdx = 0, 0  
            j = 1  

            # Step 2: Iterate through the array to find fractions smaller than mid  
            for i in range(n - 1):  

                # Move j to find the first fraction greater than mid  
                while j < n and arr[i] >= mid * arr[j]:  
                    j += 1  

                # Count the number of fractions smaller than mid  
                totalSmallerFractions += (n - j)  

                # If j reaches the end, break out of the loop  
                if j == n:  
                    break  

                # Calculate the current fraction  
                fraction = float(arr[i]) / arr[j]  

                # Update maxFraction and store the indices if it's the largest found  
                if fraction > maxFraction:  
                    numeratorIdx = i  
                    denominatorIdx = j  
                    maxFraction = fraction  

            # Step 3: Check if we found exactly k fractions smaller than mid  
            if totalSmallerFractions == k:  
                return [arr[numeratorIdx], arr[denominatorIdx]]  

            # If we found more than k, search in the left half  
            elif totalSmallerFractions > k:  
                right = mid  

            # If we found fewer than k, search in the right half  
            else:  
                left = mid  

        # Return an empty list if k-th fraction is not found  
        return []

Javascript 
// Approach: Binary Search with Two Pointers  
// Language: JavaScript  

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function(arr, k) {
    
    // Get the size of the array
    let n = arr.length;
    
    // Define the binary search range for fraction values
    let left = 0.0, right = 1.0;
    
    // Perform binary search to find the k-th smallest fraction
    while (left < right) {
        
        // Calculate the middle value
        let mid = (left + right) / 2;
        
        // Initialize variables to track the best fraction found
        let maxFraction = 0.0;
        let totalSmallerFractions = 0;
        let numeratorIdx = 0, denominatorIdx = 0;
        let j = 1;
        
        // Step 1: Iterate through the array to find fractions smaller than mid
        for (let i = 0; i < n - 1; i++) {
            
            // Move j to find the first fraction greater than mid
            while (j < n && arr[i] >= mid * arr[j]) {
                j++;
            }
            
            // Count the number of fractions smaller than mid
            totalSmallerFractions += (n - j);
            
            // If j reaches the end, break out of the loop
            if (j === n) break;
            
            // Calculate the current fraction
            let fraction = arr[i] / arr[j];
            
            // Update maxFraction and store the indices if it's the largest found
            if (fraction > maxFraction) {
                numeratorIdx = i;
                denominatorIdx = j;
                maxFraction = fraction;
            }
        }
        
        // Step 2: Check if we found exactly k fractions smaller than mid
        if (totalSmallerFractions === k) {
            return [arr[numeratorIdx], arr[denominatorIdx]];
        }
        
        // If we found more than k, search in the left half
        else if (totalSmallerFractions > k) {
            right = mid;
        }
        
        // If we found fewer than k, search in the right half
        else {
            left = mid;
        }
    }
    
    // Return an empty array if k-th fraction is not found
    return [];
};

Time Complexity Analysis: O(n⋅log(m))

Let n be the size of the input array and m be the maximum value in the array.

Time Complexity: O(n⋅log(m))

  • The algorithm uses binary search. Within each iteration of the binary search, we perform a linear scan through the array to count the number of fractions smaller than the current mid value. Since the array is sorted, this linear scan takes O(n) time.
  • Binary search takes O(logx) where x is the number of elements in the search space because each iteration reduces the size of the search space by half. We will stop generating fractions and terminate the search when the total number of smaller fractions equals k. This will happen when the size of the search space becomes smaller than the smallest possible difference between two fractions, which is 1/m^2
  • This means the size of the search space can be up to m^2 . Therefore, the total time complexity is O(n⋅log(m ^2)).which simplifies to O(n⋅log(m)).

Final Time Complexity: O(n⋅log(m))

Space Complexity Analysis: O(M + N)

Sorting and Storage (O(M + N))

  • The stream list stores all elements from the initial nums array (N) and the incoming add() calls (M), requiring O(M + N) space.

Auxiliary Space (O(1))

  • Binary search runs in-place and does not use extra memory.
  • Insertion modifies the existing list rather than creating a new one.
  • No additional data structures (like heaps or extra arrays) are used, keeping auxiliary space at O(1).

Final Space Complexity:O(M + N)

  • The total space required is due to maintaining the sorted list, resulting in O(M + N) overall space complexity.
The initial approach involved generating and storing all possible fractions, which required handling a large number of elements at once. To optimize, we use a min-heap, which allows us to efficiently track only the k smallest fractions at any given time. Instead of sorting all fractions beforehand, we dynamically update the heap, ensuring that the k-th smallest fraction is always accessible. This shift reduces unnecessary storage and improves retrieval efficiency.

Optimal Approach

Intuition

The binary search approach involves iterating through the array for each fraction being tested, which can be time-consuming, especially for large arrays. To optimize this process, we can leverage the property that the smallest fractions will be formed by dividing each element by the largest element in the array. This observation leads us to the idea of using a priority queue data structure, which can efficiently maintain and update the smallest fractions as we explore the search space.

For a sorted input array where each element is distinct, the possible fractions are formed by selecting a numerator and a denominator from different positions in the array. The key observation is that the smallest fractions are created by dividing the smallest numbers in the array by the largest numbers. This allows us to structure our search in a way that always prioritizes the smallest fractions first.

Instead of generating and sorting all possible fractions, we initialize a priority queue to keep track of the smallest fractions dynamically. Each fraction is represented as a pair consisting of a numerator and a denominator, and the priority queue ensures that the smallest fraction remains at the top. Since the array is sorted, the initial fractions are formed by pairing each numerator with the last element of the array as the denominator. This guarantees that the first fractions introduced into the queue are the smallest possible ones.

Once the priority queue is populated, the smallest fraction is extracted. To continue exploring fractions in increasing order, a new fraction is introduced by replacing the extracted fraction with another one that has the same numerator but a smaller denominator. This is done by decrementing the denominator index, ensuring that the newly added fraction is still larger than the previous smallest fraction but remains among the smallest available fractions. This process continues until the k-th smallest fraction is found.

The reason for decrementing the denominator instead of incrementing the numerator is that fractions need to be processed in ascending order. If we were to fix the denominator and increment the numerator, we would generate larger fractions first, making it harder to efficiently track the k-th smallest fraction. By fixing the numerator and decreasing the denominator, we systematically explore the smallest fractions first while maintaining the natural ordering of fractions.

At each step, the priority queue helps in efficiently identifying the smallest available fraction while ensuring that unnecessary computations are avoided. The extracted fraction is replaced with the next smallest fraction from the sequence, and after k extractions, the k-th smallest fraction will be at the top of the queue. This structured approach significantly reduces computational complexity compared to brute-force methods and ensures that only relevant fractions are considered during the search.

Approach

Step 1: Initialize Priority Queue

  • Create an empty priority queue (min-heap) to store fractions along with their corresponding indices.
  • The priority queue is structured to keep the smallest fraction at the top.

Step 2: Populate Initial Fractions

  • Iterate through the array and compute fractions by dividing each element by the largest element in the array.
  • Push each fraction into the priority queue as a pair containing its negative value (to maintain ascending order) and its indices (numerator and denominator).

Step 3: Extract and Replace Fractions

  • Perform k−1 iterations to remove the smallest fraction from the priority queue.
  • Extract the top element from the heap, which represents the current smallest fraction.
  • Decrement the denominator index to form a new fraction while keeping the numerator unchanged.
  • Push the newly formed fraction back into the priority queue to maintain order.

Step 4: Retrieve the k-th Smallest Fraction

  • After k−1 extractions, the top element of the priority queue represents the k-th smallest fraction.
  • Extract the indices from the top element and return the corresponding numerator and denominator as the result.

Dry Run

Input: arr = [1,2,3,5], k = 3

Expected Output: arr = [2,5]

  • We need to determine the k-th smallest fraction by systematically exploring and extracting fractions in ascending order.

Step 1: Initialize Priority Queue

  • We start with an empty min-heap (priority queue) to store fractions and their indices.
  • Heap Initialization:
  • We consider fractions where the denominator is initially the last element (5):
  • 1/5 = 0.2 → (-0.2, (0,3))
  • 2/5 = 0.4 → (-0.4, (1,3))
  • 3/5 = 0.6 → (-0.6, (2,3))
  • Heap after insertion (sorted by fraction values):
  • [(-0.2, (0,3)), (-0.4, (1,3)), (-0.6, (2,3))]

Step 2: Extract k-th Smallest Fraction

  • We perform k-1 extractions to find the k-th smallest fraction.
  • First Extraction (1st smallest fraction):
  • Extract (-0.2, (0,3)) → 1/5 is the smallest fraction.
  • Replace it with a new fraction by decrementing the denominator index (from 5 to 3):
  • 1/3 = 0.3333 → (-0.3333, (0,2))
  • Push into the heap.
  • Updated Heap:
  • [(-0.3333, (0,2)), (-0.4, (1,3)), (-0.6, (2,3))]
  • Second Extraction (2nd smallest fraction):
  • Extract (-0.3333, (0,2)) → 1/3 is the second smallest fraction.
  • Replace it with a new fraction by decrementing the denominator index (from 3 to 2):
  • 1/2 = 0.5 → (-0.5, (0,1))
  • Push into the heap.
  • Updated Heap:
  • [(-0.4, (1,3)), (-0.5, (0,1)), (-0.6, (2,3))]
  • Third Extraction (3rd smallest fraction - Final Answer):
  • Extract (-0.4, (1,3)) → 2/5 is the third smallest fraction.

Step 3: Return the Result

  • The extracted fraction is 2/5, which is the k-th smallest fraction.

Final Output: [2/5]

Code for All Languages
C++ 
// Approach: Min Heap (Priority Queue) to Find k-th Smallest Prime Fraction  
// Language: C++  

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:

    // Step 1: Find k-th smallest fraction using Min Heap  
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        
        // Min Heap to store fractions in ascending order
        priority_queue<pair<double, pair<int, int>>> pq;

        // Insert fractions where the denominator is the largest element
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            pq.push({-1.0 * arr[i] / arr[n - 1], {i, n - 1}});
        }

        // Step 2: Extract k-1 smallest fractions and push next possible fraction
        while (--k > 0) {
            
            // Remove the smallest fraction
            pair<int, int> cur = pq.top().second;
            pq.pop();

            // Move to the next smallest possible fraction  
            if (cur.second - 1 > cur.first) {
                pq.push({-1.0 * arr[cur.first] / arr[cur.second - 1], 
                        {cur.first, cur.second - 1}});
            }
        }

        // Step 3: Retrieve the k-th smallest fraction
        pair<int, int> result = pq.top().second;
        return {arr[result.first], arr[result.second]};
    }
};

Java 
// Approach: Min Heap (Priority Queue) to Find k-th Smallest Prime Fraction  
// Language: Java  

import java.util.*;

class Solution {
    
    // Step 1: Find k-th smallest fraction using Min Heap  
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        
        // Min Heap to store fractions in ascending order
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));

        // Insert fractions where the denominator is the largest element
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            pq.offer(new double[] {
                -1.0 * arr[i] / arr[n - 1], 
                i, 
                n - 1
            });
        }

        // Step 2: Extract k-1 smallest fractions and push next possible fraction
        while (--k > 0) {
            
            // Remove the smallest fraction
            double[] cur = pq.poll();
            int numeratorIndex = (int) cur[1];
            int denominatorIndex = (int) cur[2] - 1;

            // Move to the next smallest possible fraction  
            if (denominatorIndex > numeratorIndex) {
                pq.offer(new double[] {
                        -1.0 * arr[numeratorIndex] / arr[denominatorIndex], 
                        numeratorIndex, 
                        denominatorIndex
                });
            }
        }

        // Step 3: Retrieve the k-th smallest fraction
        double[] result = pq.poll();
        return new int[]{arr[(int) result[1]], arr[(int) result[2]]};
    }
}

Python 
# Approach: Min Heap (Priority Queue) to Find k-th Smallest Prime Fraction  
# Language: Python  

import heapq

class Solution(object):
    
    def kthSmallestPrimeFraction(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        # Step 1: Min Heap to store fractions in ascending order
        min_heap = []
        n = len(arr)

        # Insert fractions where the denominator is the largest element
        for i in range(n - 1):
            heapq.heappush(min_heap, (arr[i] / float(arr[-1]), i, n - 1))

        # Step 2: Extract k-1 smallest fractions and push next possible fraction
        for _ in range(k - 1):
            
            # Remove the smallest fraction
            _, num_idx, den_idx = heapq.heappop(min_heap)

            # Move to the next smallest possible fraction  
            if den_idx - 1 > num_idx:
                heapq.heappush(min_heap, (arr[num_idx] / float(arr[den_idx - 1]), num_idx, den_idx - 1))

        # Step 3: Retrieve the k-th smallest fraction
        _, num_idx, den_idx = heapq.heappop(min_heap)
        return [arr[num_idx], arr[den_idx]]

Javascript 
// Approach: Min Heap (Priority Queue) to Find k-th Smallest Prime Fraction  
// Language: JavaScript  

class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Insert an element into the heap
    push(element) {
        this.heap.push(element);
        this.heap.sort((a, b) => a[0] - b[0]); // Sort by fraction value
    }

    // Remove and return the smallest element
    pop() {
        return this.heap.shift();
    }

    // Return the smallest element without removing it
    top() {
        return this.heap[0];
    }

    // Return the size of the heap
    size() {
        return this.heap.length;
    }
}

/**
 * @param {number[]} arr - The sorted prime array
 * @param {number} k - The k-th smallest fraction to find
 * @return {number[]} - The k-th smallest fraction as [numerator, denominator]
 */
var kthSmallestPrimeFraction = function(arr, k) {
    let minHeap = new MinHeap();
    let n = arr.length;

    // Step 1: Insert fractions where the denominator is the largest element
    for (let i = 0; i < n - 1; i++) {
        minHeap.push([arr[i] / arr[n - 1], i, n - 1]);
    }

    // Step 2: Extract k-1 smallest fractions and push next possible fraction
    for (let i = 0; i < k - 1; i++) {
        let [_, numIdx, denIdx] = minHeap.pop();

        // Move to the next smallest possible fraction
        if (denIdx - 1 > numIdx) {
            minHeap.push([arr[numIdx] / arr[denIdx - 1], numIdx, denIdx - 1]);
        }
    }

    // Step 3: Retrieve the k-th smallest fraction
    let [_, numIdx, denIdx] = minHeap.pop();
    return [arr[numIdx], arr[denIdx]];
};

Time Complexity Analysis: O((n+k)⋅logn)

Let n be the size of the input array and k be the integer k.

Time Complexity: O((n+k)⋅logn)

  • Pushing the initial fractions into the priority queue takes O(nlogn).
  • Iteratively removing and replacing fractions takes O(klogn) and retrieving the kthsmallest fraction takes O(logn).

Thus the overall time complexity of the algorithm is O(nlogn+klogn), which can write as O((n+k)⋅logn)

Space Complexity Analysis: O(k)

Min Heap Storage (O(k))

  • The min heap maintains at most k elements at any time.
  • Since we only store k fractions (numerator/denominator pairs), the heap never exceeds O(k) space.

Input Storage (O(n)) (not counted in auxiliary space complexity)

  • The input array nums is provided externally and does not count toward additional space usage.
  • The heap stores only indices (not elements themselves), avoiding extra space usage.

Auxiliary Space (O(1))

  • The heap operations (insertion and deletion) are performed in-place, requiring only a few extra variables (k, val).
  • No additional data structures or recursive calls are used.

Final Space Complexity:O(K)

  • The dominant factor is the min heap size, which is limited to k, making the overall space complexity O(k).

Similar Problems

Now we have successfully tackled this problem, let’s try these similar problems.

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.Note that it is the kth largest element in the sorted order, not the kth distinct element.

Find Median from Data Stream

This problem requires continuously finding the median of a growing data stream. It uses two heaps (a max-heap for the left half and a min-heap for the right half) to efficiently balance and retrieve the median in O(log n) insertion and O(1) retrieval time, similar to how we maintain the k-th largest element in a min-heap.