In this article, we will dive into solving the problem of finding the K pairs with the smallest sums from two given integer arrays sorted in non-decreasing order. We will explore a detailed explanation of the problem, a brute force approach (if applicable), and a more efficient approach using a Min-Heap. Let’s dive in!
If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!
Understanding the Problem
Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k, our goal is to find the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums, where each pair consists of one element from nums1 and one element from nums2.
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]
Using Efficient Approach (Min-Heap)
The Min-Heap approach allows us to efficiently manage and retrieve the smallest sums among the possible pairs. By pushing the smallest pairs into the heap and expanding the search gradually, we can ensure that we are always considering the smallest available pairs at each step.
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
if not nums1 or not nums2:
return []
heap = []
heapq.heappush(heap, (nums1[0] + nums2[0], 0, 0))
result = []
while heap and len(result) < k:
_, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])
if j + 1 < len(nums2):
heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
if j == 0 and i + 1 < len(nums1):
heapq.heappush(heap, (nums1[i + 1] + nums2[0], i + 1, 0))
return result
Explanation
- Initial Checks: We first check if either
nums1ornums2is empty. If either is empty, we return an empty list as there are no pairs to consider. - Heap Initialization: We initialize a Min-Heap and push the sum of the first elements of
nums1andnums2along with their indices(0, 0). - Result Storage: We create an empty list result to store the
ksmallest pairs. - Heap Processing:
- While the heap is not empty and the length of
resultis less thank, we pop the smallest sum from the heap. - We append the corresponding pair
[nums1[i], nums2[j]]to result. - If the next element in
nums2exists(j + 1 < len(nums2)), we push the sum ofnums1[i]andnums2[j + 1]along with their indices(i, j + 1)into the heap. - If we are at the start of
nums2(j == 0)and the next element innums1exists(i + 1 < len(nums1)), we push the sum ofnums1[i + 1]andnums2[0]along with their indices(i + 1, 0)into the heap.
- While the heap is not empty and the length of
- Return Result: Finally, we return the
resultlist containing thekpairs with the smallest sums.
Time Complexity: The time complexity is O(k * log k). Each insertion and extraction from the heap takes O(log k) time, and we perform up to k such operations.
Space Complexity: The space complexity is O(k) due to the space required to store the heap and the result.
Conclusion
In this article, we explored an efficient approach to solving the problem of finding the k pairs with the smallest sums from two sorted arrays. By using a Min-Heap, we managed to optimize our solution and ensure that we consider the smallest pairs first. This method is efficient and suitable for large inputs, adhering to the given constraints.
Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.
Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.
