BFS Python 104ms with comments


  • 4

    0_1467926471298_matrix.jpg
    Given the matrix for [1,7,11] and [2,4,6], we can do BFS from the top-left position to expand candidates from only right cell and bottom cell. Since we treat it as a graph, we need to skip visited vertices as I used a dictionary visited.

    class Solution(object):
        def kSmallestPairs(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[List[int]]
            """
            import heapq
            ret = []
            if len(nums1) * len(nums2) > 0:
                queue = [(nums1[0] + nums2[0], (0, 0))]
                visited = {}
                while len(ret) < k and queue:
                    _, (i, j) = heapq.heappop(queue)
                    ret.append((nums1[i], nums2[j]))
                    if j + 1 < len(nums2) and (i, j + 1) not in visited:
                            heapq.heappush(queue, (nums1[i] + nums2[j + 1], (i, j + 1)))
                            visited[(i, j + 1)] = 1
                    if i + 1 < len(nums1) and (i + 1, j) not in visited:
                            heapq.heappush(queue, (nums1[i + 1] + nums2[j], (i + 1, j)))
                            visited[(i + 1, j)] = 1
            return ret
    

  • 0
    Z

    is this k*log(k) solution?


  • 1

    Yeah, I think so.


Log in to reply
 

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