MediumNo. 0786

K-th Smallest Prime Fraction — LeetCode 786 Python Solution

Topics
Array, Two Pointers, Binary Search, Sorting, Heap (Priority Queue)
Reading time
2 min

The problem

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.

Example

Input
arr = [1,2,3,5], k = 3
Output
[2,5]
Explanation
The fractions to be considered in sorted order are:

Python solution

PythonSolution
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]
        heapify(h)
        for _ in range(k - 1):
            _, i, j = heappop(h)
            if i + 1 < j:
                heappush(h, (arr[i + 1] / arr[j], i + 1, j))
        return [arr[h[0][1]], arr[h[0][2]]]

Complexity

Time
O(n) (after optional sort O(n log n))
Space · auxiliary
O(1)

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 786. K-th Smallest Prime Fraction is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 786. K-th Smallest Prime Fraction?

LeetCode 786. K-th Smallest Prime Fraction is rated Medium on LeetCode.

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

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 786. K-th Smallest Prime Fraction?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 786. K-th Smallest Prime Fraction cover?

LeetCode 786. K-th Smallest Prime Fraction is tagged Array, Two Pointers, Binary Search, Sorting and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.