373.Find_K_Pairs_with_Smallest_Sums(Medium).md

373. Find K Pairs with Smallest Sums (Medium)

Date and Time: Feb 1, 2025, 11:00 (EST)

Link: https://leetcode.com/problems/find-k-pairs-with-smallest-sums

Question:

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Output: [[1,2],[1,4],[1,6]]

Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Output: [[1,1],[1,1]]

Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Constraints:

• 1 <= nums1.length, nums2.length <= 10^5

• -10^9 <= nums1[i], nums2[i] <= 10^9

• nums1 and nums2 both are sorted in non-decreasing order.

• 1 <= k <= 10^4

• k <= nums1.length * nums2.length

Walk-through:

1. Use minHeap minHeap[] to save the sum of every elements from nums1 with the first index of nums2, save [sum, 0] into minHeap.

2. Use while loop for k > 0 and minHeap to add the smallest pair we pop from minHeap[], then we add the next element of nums2 with the current val from nums1 by sum-nums2[j]. So we add [sum-nums2[j]+nums2[j+1], j+1], and we repeat this process, so we are guaranteed to get the next smallest sum, which is not necessary to be the next element of nums2. (Example 2)

Python Solution:

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # Use heap to store [sum, first index of nums2] for all elements from nums1
        # Add the pair to res[], add the next pair of current i from nums1 with the next element from nums2 to heap
        # Repeat until k=0 or tmp[] is out

        # TC: O(m*logm + min(m, k) * logm), m=len(nums1), SC: O(m+k)
        minHeap, res = [], []
        # Add pairs of [sum, first index of nums2] for nums1
        for i in nums1:
            heapq.heappush(minHeap, [i+nums2[0], 0])
        while k > 0 and minHeap:
            val, j = heapq.heappop(minHeap)
            i = val - nums2[j]
            res.append([i, nums2[j]])
            # Add the next val from nums2
            if j+1 < len(nums2):
                heapq.heappush(minHeap, [i+nums2[j+1],j+1])
            k -= 1
        return res

Time Complexity: $O(m*logm + min(m, k) * logm)$
Space Complexity: $O(m + k)$