Problem Description

You have a sorted array arr that contains the number 1 and prime numbers. All numbers in the array are unique. You also have an integer k.

The task is to consider all possible fractions formed by dividing elements in the array. Specifically, for every pair of indices i and j where i < j, you form the fraction arr[i] / arr[j].

Once you have all these fractions, you need to find the k-th smallest fraction among them. The answer should be returned as an array of two integers [arr[i], arr[j]], representing the numerator and denominator of that k-th smallest fraction.

For example, if arr = [1, 2, 3, 5], the possible fractions would be:

• 1/2, 1/3, 1/5 (fractions with numerator 1)
• 2/3, 2/5 (fractions with numerator 2)
• 3/5 (fraction with numerator 3)

These fractions in ascending order would be: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. So if k = 3, the answer would be [2, 5] since 2/5 is the 3rd smallest fraction.

The solution uses a min-heap approach where it starts with the smallest possible fractions (those with numerator arr[0] = 1) and incrementally explores larger fractions by advancing the numerator index while keeping the denominator fixed, maintaining the k smallest fractions seen so far.

Intuition

The key insight is that since the array is sorted, for any fixed denominator arr[j], the fractions arr[0]/arr[j], arr[1]/arr[j], ..., arr[j-1]/arr[j] are in increasing order. This property allows us to avoid generating and sorting all possible fractions.

Think of it this way: if we were to list all fractions with denominator arr[j], they would increase as we move the numerator from left to right in the array. Similarly, for a fixed numerator arr[i], the fractions decrease as we move the denominator from left to right (since we're dividing by larger numbers).

This leads us to a pattern similar to merging k sorted lists. We can start with the smallest possible fractions - those with the smallest numerator (arr[0] = 1) paired with each denominator. These are 1/arr[1], 1/arr[2], ..., 1/arr[n-1], which we know are sorted in decreasing order.

We use a min-heap to always extract the smallest fraction among our candidates. When we pop a fraction arr[i]/arr[j] from the heap, we know the next larger fraction with the same denominator arr[j] would be arr[i+1]/arr[j] (if it exists). By adding this next fraction to the heap, we ensure we're always considering the smallest unprocessed fractions.

This approach is efficient because:

1. We don't generate all O(n²) fractions upfront
2. We only generate fractions as needed, maintaining at most O(n) fractions in the heap at any time
3. We leverage the sorted property of the array to systematically explore fractions in increasing order

The process continues until we've popped k-1 fractions from the heap. The fraction at the top of the heap after k-1 pops is our answer - the k-th smallest fraction.

Learn more about Two Pointers, Binary Search, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a min-heap data structure to efficiently find the k-th smallest fraction without generating all possible fractions.

Step 1: Initialize the heap

h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]

We start by creating initial heap entries. For each element arr[j] where j > 0, we create a tuple containing:

• The fraction value: 1/arr[j] (since arr[0] = 1)
• The numerator index: 0 (pointing to arr[0])
• The denominator index: j + 1 (adjusted because we enumerate from arr[1:])

This gives us fractions 1/arr[1], 1/arr[2], ..., 1/arr[n-1] - all fractions with the smallest possible numerator.

Step 2: Convert to heap

heapify(h)

The heapify operation arranges the list into a min-heap based on the fraction values. The smallest fraction 1/arr[n-1] will be at the root (since arr is sorted and arr[n-1] is the largest).

Step 3: Extract k-1 smallest fractions

for _ in range(k - 1):
    _, i, j = heappop(h)
    if i + 1 < j:
        heappush(h, (arr[i + 1] / arr[j], i + 1, j))

We pop the smallest fraction k-1 times. Each time we pop a fraction arr[i]/arr[j]:

• We check if there's a next fraction with the same denominator: arr[i+1]/arr[j]
• The condition i + 1 < j ensures we don't create invalid fractions where the numerator index meets or exceeds the denominator index
• If valid, we push this next fraction into the heap

This process maintains the invariant that the heap always contains the smallest unprocessed fraction for each "chain" of fractions with the same denominator.

Step 4: Return the k-th smallest fraction

return [arr[h[0][1]], arr[h[0][2]]]

After popping k-1 fractions, the root of the heap contains the k-th smallest fraction. We extract the numerator and denominator indices from the tuple and return the corresponding array values.

Time Complexity: O(k log n) where we perform at most k heap operations, each taking O(log n) time.

Space Complexity: O(n) for storing at most n-1 fractions in the heap at any time.

Example Walkthrough

Let's walk through finding the 4th smallest fraction with arr = [1, 2, 3, 5] and k = 4.

Step 1: Initialize heap with fractions having numerator 1

We start with all fractions where numerator is arr[0] = 1:

• 1/2 = 0.5 (numerator index: 0, denominator index: 1)
• 1/3 ≈ 0.333 (numerator index: 0, denominator index: 2)
• 1/5 = 0.2 (numerator index: 0, denominator index: 3)

After heapify, our min-heap looks like:

Heap: [(0.2, 0, 3), (0.333, 0, 2), (0.5, 0, 1)]
       1/5         1/3         1/2

Step 2: Extract first smallest (k=1)

Pop (0.2, 0, 3) which represents 1/5.

• Check if we can add next fraction with same denominator: arr[0+1]/arr[3] = 2/5
• Since 0+1 < 3, we add (0.4, 1, 3) to heap

Heap: [(0.333, 0, 2), (0.4, 1, 3), (0.5, 0, 1)]
       1/3           2/5         1/2

Step 3: Extract second smallest (k=2)

Pop (0.333, 0, 2) which represents 1/3.

• Check next fraction: arr[0+1]/arr[2] = 2/3
• Since 0+1 < 2, we add (0.667, 1, 2) to heap

Heap: [(0.4, 1, 3), (0.5, 0, 1), (0.667, 1, 2)]
       2/5         1/2         2/3

Step 4: Extract third smallest (k=3)

Pop (0.4, 1, 3) which represents 2/5.

• Check next fraction: arr[1+1]/arr[3] = 3/5
• Since 1+1 < 3, we add (0.6, 2, 3) to heap

Heap: [(0.5, 0, 1), (0.6, 2, 3), (0.667, 1, 2)]
       1/2         3/5         2/3

Step 5: Return the 4th smallest

After extracting k-1 = 3 fractions, the root of heap (0.5, 0, 1) represents the 4th smallest fraction.

• Numerator: arr[0] = 1
• Denominator: arr[1] = 2
• Answer: [1, 2]

The fractions we encountered in order were: 1/5, 1/3, 2/5, and our answer 1/2 - exactly the 4th smallest fraction.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k * log n) where n is the length of the input array and k is the given parameter.

• Initial heap construction: Creating the initial heap with n-1 elements (fractions with numerator arr[0] and all other elements as denominators) takes O(n) time for list creation and O(n) for heapification.
• Main loop: The loop runs exactly k-1 times. In each iteration:
  • heappop() operation: O(log n) since the heap can contain at most n-1 elements
  • heappush() operation: O(log n) for the same reason
• Final answer extraction: O(1) to access the minimum element from the heap
• Overall: O(n) + O(k * log n) = O(n + k * log n)
• Since typically k ≤ n(n-1)/2 and often k is much smaller, the dominant term is usually O(k * log n) when k > n, otherwise O(n) dominates for small k.

Space Complexity: O(n) where n is the length of the input array.

• The heap initially contains n-1 elements (one fraction for each element except the first as denominator)
• Throughout execution, the heap size never exceeds n-1 elements because:
  • We start with n-1 fractions
  • Each heappop() removes one element and each heappush() adds at most one element
  • The heap maintains at most one fraction for each possible denominator
• Therefore, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Mapping When Initializing the Heap

One of the most common mistakes is incorrectly mapping indices when creating the initial heap entries. The original solution uses:

h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]

The pitfall occurs when developers forget that enumerate(arr[1:]) starts counting from 0, but these indices correspond to elements starting from position 1 in the original array. This leads to confusion about whether to use j or j + 1 for the denominator index.

Incorrect attempt:

# Wrong: Using j directly instead of j + 1
heap = [(arr[0] / arr[j], 0, j) for j in range(1, len(arr))]
# This would incorrectly map to arr[1], arr[2], ... arr[n-2] as denominators

Correct solution:

# Clear and explicit indexing
heap = [(arr[0] / arr[j], 0, j) for j in range(1, len(arr))]
# Now j directly represents the index in the original array

2. Off-by-One Error in the Boundary Check

Another common mistake is using the wrong comparison operator when checking if we can create the next fraction:

Incorrect:

if i + 1 <= j:  # Wrong: allows i + 1 == j
    heappush(h, (arr[i + 1] / arr[j], i + 1, j))

This would allow creating fractions where the numerator and denominator are the same element (when i + 1 == j), resulting in a fraction equal to 1, which violates the problem constraint that i < j.

Correct:

if i + 1 < j:  # Ensures numerator index is strictly less than denominator index
    heappush(h, (arr[i + 1] / arr[j], i + 1, j))

3. Accessing Heap After All Elements Are Popped

If k equals the total number of possible fractions, the loop might pop all elements from the heap, leaving it empty:

Problematic scenario:

for _ in range(k - 1):
    _, i, j = heappop(h)
    if i + 1 < j:
        heappush(h, (arr[i + 1] / arr[j], i + 1, j))
# If heap is empty here, h[0] will raise an IndexError
return [arr[h[0][1]], arr[h[0][2]]]

Robust solution:

# Store the last popped element
for _ in range(k - 1):
    fraction_value, i, j = heappop(h)
    if i + 1 < j:
        heappush(h, (arr[i + 1] / arr[j], i + 1, j))

# Check if heap is empty (edge case)
if not h:
    # Return the last popped fraction
    return [arr[i], arr[j]]
else:
    return [arr[h[0][1]], arr[h[0][2]]]

4. Integer Division Instead of Float Division

In Python 2 or when using floor division, this could be a problem:

Incorrect (Python 2 style):

# This would perform integer division in Python 2
heap = [(1 / arr[j], 0, j) for j in range(1, len(arr))]

Correct (Python 3 compatible):

# Ensure float division
heap = [(float(arr[0]) / arr[j], 0, j) for j in range(1, len(arr))]
# Or use: arr[0] * 1.0 / arr[j]

5. Not Handling Edge Cases

The solution should handle edge cases like:

• k = 1: Should return the smallest fraction without any heap pops
• Array with only 2 elements: Only one possible fraction
• Very large arrays where numerical precision might be an issue

Enhanced solution with edge case handling:

def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
    n = len(arr)
  
    # Edge case: only one fraction possible
    if n == 2:
        return arr
  
    # Initialize heap
    heap = [(arr[0] / arr[j], 0, j) for j in range(1, n)]
    heapify(heap)
  
    # Handle k = 1 case efficiently
    if k == 1:
        return [arr[0], arr[-1]]
  
    # Process k-1 smallest fractions
    for _ in range(k - 1):
        if not heap:
            break
        _, i, j = heappop(heap)
        if i + 1 < j:
            heappush(heap, (arr[i + 1] / arr[j], i + 1, j))
  
    # Return the k-th smallest
    return [arr[heap[0][1]], arr[heap[0][2]]] if heap else [arr[i], arr[j]]