NUHMAN.com

📘 Problem Statement

You are given two sorted integer arrays nums1 and nums2 and a number k. Your task is to find the k pairs with the smallest sums, where each pair consists of one element from nums1 and one element from nums2. Return a list of these k pairs in ascending order of their sums.

🧠 Key Insight

Since the arrays nums1 and nums2 are both sorted, we can efficiently find the smallest sums using a min-heap. The min-heap helps us efficiently extract the smallest sum pairs, and by keeping track of the indices of the elements in the heap, we can generate the next smallest sum pair.

Steps:

1. Initialize the Min-Heap: Start by pushing the smallest possible sum into the heap, which is formed by the first elements of both arrays.
2. Heap Operations: Extract the smallest sum from the heap, and add the next possible sum by incrementing the index of the second array (nums2) while keeping the index of nums1 fixed.
3. Repeat: Continue extracting pairs from the heap and adding new pairs until we have k pairs or exhaust the heap.

This approach works efficiently with a time complexity of O(k log k), where k is the number of pairs to find, and the space complexity is O(k) due to the heap.

💡 Approach

1. Use a Min-Heap: The min-heap will store pairs of the form (sum, i, j) where i is an index in nums1 and j is an index in nums2.
2. Heap Initialization: Start by pushing the smallest possible pair (nums1[0] + nums2[0], 0, 0) into the heap.
3. Iterate and Generate Pairs: At each step, pop the heap to get the smallest sum and then push the next pair generated by incrementing the index of nums2 or nums1.

🐍 Python Code

python

import heapq

class Solution:
    def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
        # Edge case where either of the arrays is empty or k is 0
        if not nums1 or not nums2 or k == 0:
            return []
        
        min_heap = []
        result = []
        
        # Initialize the min-heap with the first row (first element of nums1 and all elements of nums2)
        for i in range(min(k, len(nums1))):  # We only need at most k rows
            heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
        
        # Extract k smallest pairs from the heap
        while k > 0 and min_heap:
            sum_value, i, j = heapq.heappop(min_heap)
            result.append([nums1[i], nums2[j]])
            k -= 1
            
            # If there is a next element in nums2 for the current pair, push it to the heap
            if j + 1 < len(nums2):
                heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
        
        return result

🔍 Step-by-Step Explanation

1. Edge Case Handling

python

if not nums1 or not nums2 or k == 0:
    return []

• First, we handle edge cases where either of the arrays is empty or k is zero. In these cases, we return an empty list since there are no pairs to find.

2. Initialize the Min-Heap

python

min_heap = []
for i in range(min(k, len(nums1))):
    heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))

• We initialize the min-heap with pairs formed by the elements of nums1 (from index 0 to min(k, len(nums1))), paired with the first element of nums2. Each pair in the heap is represented as (sum, i, j) where:
• sum = nums1[i] + nums2[j]
• i is the index of the element in nums1
• j is the index of the element in nums2

3. Heap Extraction and Pair Generation

python

while k > 0 and min_heap:
    sum_value, i, j = heapq.heappop(min_heap)
    result.append([nums1[i], nums2[j]])
    k -= 1

• We extract the smallest sum pair from the heap. After popping the heap, we append the pair [nums1[i], nums2[j]] to the result.
• We decrement k to keep track of how many pairs we have found.

4. Push the Next Pair in the Sequence

python

if j + 1 < len(nums2):
    heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))

• If there is a next element in nums2 for the current index i, we push the next pair into the heap: (nums1[i] + nums2[j + 1], i, j + 1).

5. Return the Result

python

return result

• Finally, we return the list of k smallest sum pairs.

💡 Example

python

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

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

Explanation:
The three smallest pairs are:
1. [1, 2] -> Sum: 3
2. [1, 4] -> Sum: 5
3. [1, 6] -> Sum: 7

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(k log k)Space ComplexityO(k)

• Time Complexity: The algorithm uses a min-heap of size k and performs heap operations (push and pop) for each of the k smallest pairs, leading to a time complexity of O(k log k).
• Space Complexity: The space complexity is O(k) due to the heap storing at most k pairs at any given time.

🧵 Final Thoughts

This problem is a great example of how min-heaps can be leveraged to solve problems efficiently, especially when working with sorted arrays and finding pairs or ranges with minimal values.

• Min-Heap: The heap allows us to efficiently track and extract the smallest sum pairs, even as we progress through the arrays.
• Efficient Pair Generation: By pushing the next pair in sequence to the heap, we avoid unnecessary recomputation, making the algorithm efficient even for large inputs.

This solution ensures that we are both time-efficient and space-efficient, making it suitable for a variety of use cases involving sorted arrays and pair-based problems.