# Python solution with detailed explanation

• Solution

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

Similar Problems

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)))
if y1+1 < M and (x1,y1+1) not in seen:
heappush(heap, (nums1[x1]+nums2[y1+1], (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
``````

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