Python solution with detailed explanation


  • 0
    G

    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)))
                    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
    

Log in to reply
 

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