# Python solution using heapq

• ``````import heapq
class Solution(object):
def kSmallestPairs(self, nums1, nums2, k):
if len(nums1)*len(nums2) <= k:
return [[i, j] for i in nums1 for j in nums2]
hp = [[n + nums2[0], n, 0] for n in nums1]
res = []
for i in range(k):
psum, n, ind = hp[0]
res.append([n, psum - n])
if ind + 1 == len(nums2):
heapq.heappop(hp)
else:
heapq.heapreplace(hp, [n + nums2[ind+1], n, ind+1])
return res
``````

• why you have

`````` if len(nums1)*len(nums2) <= k:
return [[i, j] for i in nums1 for j in nums2]
``````

how do you know the itration of i, j for all elements in num1 and num2 will produce all pair sums in right order

• I think your code fail this case:

`num1 = [2,4,6]`
`num2 =[1,7,11]`
`k = 10`
its output is
`[[2,1],[2,7],[2,11],[4,1],[4,7],[4,11],[6,1],[6,7],[6,11]]`
while the correct order should be
`[[2,1],[4,1],[6,1],[2,7],[4,7],[2,11],[6,7],[4,11],[6,11]]`

but it get passed the OJ.

• @pennlio I don't think the problem seeks the first k pairs in a sorted order.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.