**Solution**

**Find K Pairs with Smallest Sums** https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

**Similar Problems**

- This is exactly similar to the question: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
- This post presents a visualization which allows us to understand how this problem is similar to kth smallest element in sorted array. https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions

**Solution using a set**

- Solution1 uses a set. Why do we need a set? [a,b] and [c,d]. After (a,d) is popped we add (b,d). After (c,b) we add (b,d) again. This will give up dupes.

```
from heapq import heappush, heappop
class Solution(object):
def kSmallestPairs(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[List[int]]
"""
N,M = len(nums1), len(nums2)
if N == 0 or M == 0 or k == 0:
return []
heap = [(nums1[0]+nums2[0], (0,0))]
result = []
seen =set([])
while heap:
x, (x1,y1) = heappop(heap)
result.append((nums1[x1], nums2[y1]))
if len(result) == k:
break
if x1+1 < N and (x1+1,y1) not in seen:
heappush(heap, (nums1[x1+1]+nums2[y1], (x1+1,y1)))
seen.add((x1+1,y1))
if y1+1 < M and (x1,y1+1) not in seen:
heappush(heap, (nums1[x1]+nums2[y1+1], (x1,y1+1)))
seen.add((x1,y1+1))
return result
```

**Solution adding first array and first element of second array**

Another solution is to add all sums (k or N which ever is lesser) of the first array with first element of second array into the heap. Then simply pop and add the below one in the same column. This is with respect to the diagram Stefan in the first link has shown. Here is another illustration of the idea: https://discuss.leetcode.com/topic/50885/simple-java-o-klogk-solution-with-explanation

**Another implementation of above idea with a tweak**

- Use the rule that the right side value is inserted only when we have the first row.

```
from heapq import heappush, heappop
class Solution1(object):
def kSmallestPairs(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[List[int]]
"""
N,M = len(nums1), len(nums2)
if N == 0 or M == 0 or k == 0:
return []
heap = [(nums1[0]+nums2[0], (0,0))]
result = []
while heap:
x, (x1,y1) = heappop(heap)
result.append((nums1[x1], nums2[y1]))
if len(result) == k:
break
if x1+1 < N:
heappush(heap, (nums1[x1+1]+nums2[y1], (x1+1,y1)))
if y1+1 < M and x1 == 0:
heappush(heap, (nums1[x1]+nums2[y1+1], (x1,y1+1)))
return result
```