Find K Pairs with Smallest Sums LeetCode solution in Python

1
# Runtime: 1647 ms (Top 67.28%) | Memory: 34.4 MB (Top 27.52%)
2
import heapq
3

4

5
class Solution:
6
    def kSmallestPairs(
7
        self, nums1: List[int], nums2: List[int], k: int
8
    ) -> List[List[int]]:
9

10
        ans = []
11

12
        heapq.heapify(ans)
13

14
        for i in range(min(k, len(nums1))):
15
            for j in range(min(k, len(nums2))):
16
                pairs = [nums1[i], nums2[j]]
17
                if len(ans) < k:
18
                    heapq.heappush(ans, [-(nums1[i] + nums2[j]), pairs])
19
                else:
20
                    if nums1[i] + nums2[j] > -ans[0][0]:
21
                        break
22
                    heapq.heappush(ans, [-(nums1[i] + nums2[j]), pairs])
23
                    heapq.heappop(ans)
24

25
        res = []
26
        for i in range(len(ans)):
27
            res.append(ans[i][1])
28

29
        return res