MediumNo. 0786
K-th Smallest Prime Fraction — LeetCode 786 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Two Pointers, Binary Search, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
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
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
| No. | Problem | Difficulty |
|---|---|---|
| 0658 | Find K Closest Elements | Medium |
| 0475 | Heaters | Medium |
| 0719 | Find K-th Smallest Pair Distance | Hard |
| 0825 | Friends Of Appropriate Ages | Medium |
| 1385 | Find the Distance Value Between Two Arrays | Easy |
| 1498 | Number of Subsequences That Satisfy the Given Sum Condition | Medium |
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.