Problem Description

You have two arrays of integers, nums1 and nums2, that are already sorted in non-decreasing order (smallest to largest). You also have an integer k.

Your task is to find pairs by taking one element from nums1 and one element from nums2. Among all possible pairs, you need to return the k pairs that have the smallest sums.

A pair (u, v) consists of:

• u: one element from nums1
• v: one element from nums2
• The sum of the pair is u + v

You need to return exactly k pairs with the smallest sums, formatted as (u₁, v₁), (u₂, v₂), ..., (uₖ, vₖ).

For example, if nums1 = [1, 7, 11] and nums2 = [2, 4, 6], some possible pairs would be:

• (1, 2) with sum = 3
• (1, 4) with sum = 5
• (1, 6) with sum = 7
• (7, 2) with sum = 9
• And so on...

If k = 3, you would return the 3 pairs with the smallest sums: [[1,2], [1,4], [1,6]].

The solution uses a min-heap to efficiently track and retrieve pairs with the smallest sums. It starts by pairing each element from nums1 (up to k elements) with the first element of nums2, then progressively explores pairs with larger sums by moving through nums2 for each element in nums1.

Intuition

Since both arrays are sorted, we know that the smallest possible sum must be nums1[0] + nums2[0]. But what about the second smallest? It could be either nums1[0] + nums2[1] or nums1[1] + nums2[0].

This observation leads us to think about the problem geometrically. Imagine a 2D grid where:

• Rows represent elements from nums1
• Columns represent elements from nums2
• Each cell (i, j) contains the sum nums1[i] + nums2[j]

Because both arrays are sorted, this grid has a special property: values increase as you move right (increasing j) or down (increasing i). The smallest value is at the top-left corner (0, 0).

To find the k smallest sums efficiently, we can't examine all possible pairs (that would be O(m*n)). Instead, we need a strategy to explore only the most promising candidates.

The key insight is that for any cell (i, j) we've already selected, the next smallest sums involving index i from nums1 must come from (i, j+1). Similarly, the next smallest sums involving index j from nums2 could come from (i+1, j).

A min-heap is perfect for this because it always gives us the current smallest unexplored sum. We start by adding all pairs of form (nums1[i], nums2[0]) for i from 0 to min(k-1, len(nums1)-1) to the heap. This gives us all potential starting points.

When we pop a pair (i, j) from the heap, we know it's the next smallest sum. We then push (i, j+1) to the heap if it exists, which represents the next candidate from that row. This way, we explore the grid in a controlled manner, always processing the smallest available sum next, without having to examine all possible pairs.

The reason we only move right (increasing j) and not down (increasing i) is to avoid duplicates - we've already added all necessary starting points from nums1 initially, so we only need to explore horizontally from each starting point.

Solution Approach

The solution uses a min-heap to efficiently find the k smallest pairs. Let's walk through the implementation step by step:

1. Initialize the Min-Heap

q = [[u + nums2[0], i, 0] for i, u in enumerate(nums1[:k])]
heapify(q)

We create initial heap entries by pairing each element from nums1 (up to k elements) with the first element of nums2. Each heap entry contains:

• u + nums2[0]: the sum of the pair (used as the priority key)
• i: the index in nums1
• 0: the index in nums2 (starting at 0)

We limit to nums1[:k] because we only need k pairs total, so we don't need more than k starting points.

2. Extract k Smallest Pairs

ans = []
while q and k > 0:
    _, i, j = heappop(q)
    ans.append([nums1[i], nums2[j]])
    k -= 1

We repeatedly extract the minimum element from the heap. The heap automatically gives us the pair with the smallest sum. We reconstruct the actual pair [nums1[i], nums2[j]] and add it to our answer list.

3. Add Next Candidate

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

After extracting a pair (i, j), we add the next potential pair from the same row: (i, j+1). This represents pairing the same element from nums1 with the next element from nums2. We only add it if j + 1 is within bounds.

Why This Works:

• The heap maintains the invariant that we always process the smallest unexplored sum next
• By starting with all (i, 0) pairs, we ensure every row of our conceptual grid is represented
• By only moving right (incrementing j), we avoid generating duplicate pairs
• The heap size never exceeds min(k, len(nums1)) because we only add one new element for each element we remove

Time Complexity: O(k log min(k, len(nums1))) - we perform k heap operations, each taking O(log min(k, len(nums1))) time.

Space Complexity: O(min(k, len(nums1))) for the heap storage.

Example Walkthrough

Let's walk through a concrete example with nums1 = [1, 7, 11], nums2 = [2, 4, 6], and k = 3.

Step 1: Initialize the heap We create initial pairs by combining each element from nums1 (up to k elements) with nums2[0]:

• (1, 2) with sum = 3, stored as [3, 0, 0]
• (7, 2) with sum = 9, stored as [9, 1, 0]
• (11, 2) with sum = 13, stored as [13, 2, 0]

Initial heap (min-heap based on sum):

Heap: [[3, 0, 0], [9, 1, 0], [13, 2, 0]]

Step 2: Extract first minimum (k=3) Pop [3, 0, 0] from heap → Add pair [1, 2] to answer Now we push the next candidate from this row: (0, 1) → [1+4, 0, 1] = [5, 0, 1]

Answer: [[1, 2]]
Heap: [[5, 0, 1], [9, 1, 0], [13, 2, 0]]

Step 3: Extract second minimum (k=2) Pop [5, 0, 1] from heap → Add pair [1, 4] to answer Push next candidate: (0, 2) → [1+6, 0, 2] = [7, 0, 2]

Answer: [[1, 2], [1, 4]]
Heap: [[7, 0, 2], [9, 1, 0], [13, 2, 0]]

Step 4: Extract third minimum (k=1) Pop [7, 0, 2] from heap → Add pair [1, 6] to answer Since k is now 0, we stop.

Final Answer: [[1, 2], [1, 4], [1, 6]]

The algorithm efficiently found the 3 pairs with smallest sums (3, 5, 7) without examining all 9 possible pairs. The heap ensured we always processed the smallest available sum next.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k * log(min(k, m))) where m = len(nums1) and n = len(nums2)

• Initial heap construction: We create a list of at most min(k, m) elements (one for each element in nums1[:k]), then heapify it, which takes O(min(k, m)) time
• Main loop: We perform exactly k iterations (or fewer if we run out of pairs)
  • Each iteration involves one heappop operation: O(log(heap_size))
  • Each iteration may involve one heappush operation: O(log(heap_size))
  • The heap size is bounded by min(k, m) because we start with at most min(k, m) elements and each pop-push maintains or decreases the heap size
• Total: O(min(k, m)) + O(k * log(min(k, m))) = O(k * log(min(k, m)))

Space Complexity: O(min(k, m))

• The heap q contains at most min(k, m) elements at any time, as we initially add at most k pairs from nums1 (or all of nums1 if it has fewer than k elements)
• The answer list ans stores exactly k pairs (or fewer), which is O(k) space
• Since the output space is typically not counted in space complexity analysis, the auxiliary space is O(min(k, m))

Common Pitfalls

1. Not Handling Empty Arrays

The code assumes both nums1 and nums2 are non-empty. If either array is empty, the code will crash when trying to access nums2[0].

Problem Example:

nums1 = []
nums2 = [1, 2, 3]
k = 2
# This will cause an IndexError

Solution: Add validation at the beginning of the function:

if not nums1 or not nums2:
    return []

2. Incorrect Heap Initialization Boundary

A subtle but critical pitfall is not properly limiting the initial heap size. Without nums1[:k], if len(nums1) is very large, we'd initialize the heap with all elements from nums1, which is inefficient and unnecessary.

Problem Example:

nums1 = [1, 2, 3, ..., 1000000]  # Million elements
nums2 = [1, 2]
k = 3
# Without nums1[:k], we'd create a heap with a million entries unnecessarily

Why the current solution handles this correctly: The code uses enumerate(nums1[:k]) which properly limits the initial heap size to at most k elements.

3. Forgetting to Check Bounds for nums2

When pushing new pairs to the heap, forgetting to check if index2 + 1 < len(nums2) would cause an IndexError.

Problem Example:

# If we didn't have the bounds check:
if index2 + 1 < len(nums2):  # This check is essential
    heappush(min_heap, [nums1[index1] + nums2[index2 + 1], index1, index2 + 1])

4. Using Wrong Heap Priority

A common mistake is using the wrong value as the heap priority. The heap must be ordered by the sum nums1[i] + nums2[j], not by individual values or indices.

Incorrect Implementation:

# Wrong: using just one value as priority
min_heap = [[nums1[i], i, 0] for i in range(min(k, len(nums1)))]

# Wrong: using indices as priority
min_heap = [[i, i, 0] for i in range(min(k, len(nums1)))]

Correct Implementation:

# Correct: using the sum as priority
min_heap = [[nums1[i] + nums2[0], i, 0] for i in range(min(k, len(nums1)))]

5. Not Handling k Larger Than Total Possible Pairs

When k is larger than the total number of possible pairs (len(nums1) * len(nums2)), the code should return all possible pairs rather than attempting to find more than exist.

Current solution handles this correctly with the condition while min_heap and k > 0, which stops when either:

• We've found k pairs (k reaches 0)
• We've exhausted all possible pairs (min_heap is empty)

This prevents the algorithm from running indefinitely or crashing when k exceeds the number of available pairs.