algoadvance

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from nums1 and one element from nums2.

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

Clarifying questions:

  1. What if one of the arrays is empty?
    • If either of the arrays is empty, the output should be an empty list because no pairs can be formed.
  2. What if k is greater than the total number of possible pairs?
    • Return all possible pairs sorted by their sums.
  3. What are the constraints on the size of nums1 and nums2?
    • Typically, these arrays can be quite large, up to 10^3 to 10^4 elements.
  4. Are there any constraints on the values of nums1 and nums2?
    • Values in these arrays can range between -10^9 and 10^9.

Strategy:

  1. Utilize a Min-Heap:
    • Use a Min-Heap to keep track of pairs with the smallest sums. In Python, we can use the heapq module.
    • Push pairs of elements from nums1 and nums2 into the Min-Heap with their sums as the priority.
  2. Initial Heap Population:
    • We start by pairing the first element of nums1 with every element from nums2 (or vice versa) and push these pairs into the Min-Heap.
    • This ensures that we consider pairs with the minimum possible sums first.
  3. Iterate to Gather Results:
    • Extract the smallest sum pairs from the heap up to k times or until the heap is exhausted.
  4. Avoid Redundant Pairs:
    • Use a dictionary to keep track of the indices to prevent reprocessing already considered pairs.

Code:

from heapq import heappush, heappop

def kSmallestPairs(nums1, nums2, k):
    if not nums1 or not nums2 or k == 0:
        return []
    
    min_heap = []
    res = []
    
    # Initialize the heap
    for i in range(min(len(nums1), k)):
        heappush(min_heap, (nums1[i] + nums2[0], i, 0))
    
    # Extract the smallest pairs
    while min_heap and len(res) < k:
        sum_val, i, j = heappop(min_heap)
        res.append((nums1[i], nums2[j]))
        if j + 1 < len(nums2):
            heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
    
    return res

Time Complexity:

The overall time complexity is O(k log(min(len(nums1), k))), making this approach efficient for the given problem.

Try our interview co-pilot at AlgoAdvance.com