Find K Pairs With Smallest Sums - Leetcode Solution

Problem Statement:

Given two sorted arrays nums1 and nums2, return k pairs (i, j) such that the sum of i-th element in nums1 and the j-th element in nums2 is the smallest.

Solution:

We will solve this problem with a heap. We will use min heap so that at top we get the pair with smallest sum. We will store the sums along with their indices to form unique pairs in the heap.

Steps:

1. Create a min heap to store the sums.
2. Push all pairs (nums1[i], nums2[j]) with i = 0 and j = 0 to the heap.
3. While k pairs have not been found and the heap is not empty, do the following: a. Pop the smallest sum pair from the heap (i, j). b. Add this pair to the answer list. c. Add the pairs (i+1, j) and (i, j+1) to the heap.
4. Return the answer list.

Let's see the code implementation below:

import heapq

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        
        heap = []
        
        # Push all pairs (nums1[i], nums2[j]) with i = 0 and j = 0 to the heap.
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                heapq.heappush(heap, (nums1[i] + nums2[j], i, j))
        
        res = []
        
        # Pop k smallest sum pairs from the heap
        for _ in range(k):
            if heap:
                _, i, j = heapq.heappop(heap)
                res.append([nums1[i], nums2[j]])
            else:
                break
                
        return res

Complexity Analysis:

Time complexity: O(k*log(k)). We add at most k elements to the heap, so adding one element takes O(log(k)) time. We do this k times. Additionally, at most k elements are popped from the heap. Each of these operations take O(log(k)) time.

Space complexity: O(k). The heap will store at most k pairs.

1