Domain 2MediumCORE

Find K Pairs with Smallest Sums

We are given two sorted arrays nums1 and nums2, plus an integer k. We need to find the top k pairs (u, v) where one element comes from each array such that their sum is minimized.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Heap

373. Find K Pairs with Smallest Sums

Model: qwen3.5:9b
Topics: Heap
FAANG asked: 1
Acceptance rate: 37.9%


Problem Breakdown

We are given two sorted arrays nums1 and nums2, plus an integer k. We need to find the top k pairs (u, v) where one element comes from each array such that their sum is minimized.

Key constraints:

  • Arrays are sorted ascendingly. This is critical for optimization.
  • KK is relatively small (≤1000\le 1000) compared to potential pair counts (up to N×MN \times M, where lengths can be up to 10410^4).
  • Values can be negative, but since arrays are sorted, the relative order holds regardless of sign.

Implicit edge cases:

  • What if k is larger than the total number of possible pairs? We must return all available pairs and stop early.
  • Duplicates in input arrays (e.g., [1, 1]) should be treated as distinct elements for pair generation purposes based on indices.

Intuition

A brute-force solution would generate every single combination (N×M)(N \times M), calculate sums, sort them, and slice the first KK.

  • Time Complexity: O(NMlog⁡(NM))O(NM \log(NM)) due to sorting all pairs. With lengths up to 10410^4, this is roughly 10810^8 operations, which will Time Limit Exceed (TLE).
  • We need a way to avoid generating the full matrix of sums.

Since both arrays are sorted:

  1. The smallest sum must involve nums2[0] combined with some element from nums1.
  2. If we pick (u, v) as our current best pair in row ii (where row corresponds to index ii in nums1), the next candidate for that specific row is simply (unext,v)=(nums1[i],nums2[v+index])(u_{next}, v) = (\text{nums1}[i], \text{nums2}[v+index]).
  3. We can visualize this as a matrix where rows are indices of nums1 and columns are indices of nums2. The values increase along both axes. This structure allows us to use a Min-Heap (Priority Queue) to always extract the smallest available sum without scanning everything else.

Approach

We maintain a Min-Heap that tracks candidate pairs we haven’t processed yet, ordered by their sums.

  1. Initialization: We start with nums2[0] paired against every element in nums1. However, to keep complexity low relative to KK, we only initialize the heap for indices of nums1 up to min⁡(len(nums1),k)\min(\text{len}(nums1), k). Why? Because even if there are more rows than needed, they can’t contribute to top-kk sums before their first element is processed.
  2. Heap Structure: Each entry in the heap will be a tuple: (sum_val, index_in_nums1, index_in_nums2). Python’s heapq sorts tuples lexicographically, so it naturally orders by sum first.
  3. Expansion Loop: We run exactly KK iterations (or until we exhaust all pairs).
    • Pop the smallest element (s, i, j) from heap. Add [nums1[i], nums2[j]] to results.
    • If there is a next column in nums2 (j + 1 < len(nums2)), push (nums1[i] + nums2[j+1], i, j+1) into the heap. This represents moving right along the current row of our matrix visualization.
  4. Termination: If we run out of pairs before reaching KK iterations (because k > total_pairs), stop and return what we found.

Complexity Analysis

  • Time Complexity: O(Klog⁡K)O(K \log K). We perform at most KK heap operations (pop + push). The heap size is bounded by min⁡(len(nums1),k)\min(\text{len}(nums1), k), which effectively keeps the log factor small relative to total pairs. Initialization takes O(k)O(k).
  • Space Complexity: O(K)O(K) for storing the result and the heap elements.

Solution

import heapq

def kSmallestPairs(nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
    # Edge case check (though constraints say lengths >= 1, good practice to handle empty logic implicitly via loops)
    if not nums1 or not nums2 or k == 0:
        return []

    n = len(nums1)
    m = len(nums2)
    
    # Heap stores tuples of (sum_val, index_in_nums1, index_in_nums2)
    heap = []
    
    # Initialize with the first element from nums2 paired with up to k elements from nums1.
    # We limit by min(n, k) because we only need top-k pairs total; 
    # any row beyond this won't be needed for the top-k sums unless previous rows are exhausted.
    for i in range(min(k, n)):
        heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))

    result = []
    
    while len(result) < k and heap:
        # Pop the pair with smallest sum
        _, r_idx, c_idx = heapq.heappop(heap)
        
        # Add to results
        result.append([nums1[r_idx], nums2[c_idx]])
        
        # If there is a next element in nums2 for this row (r_idx), add it to heap.
        if c_idx + 1 < m:
            heapq.heappush(heap, (nums1[r_idx] + nums2[c_idx + 1], r_idx, c_idx + 1))

    return result

Edge Cases Handled

  • k>total pairsk > \text{total pairs}: The loop condition len(result) < k and heap ensures we stop when the heap is empty (all combinations exhausted), returning all available valid pairs.
  • Small arrays / Large KK: Logic handles cases where total possible pairs are fewer than requested KK.
  • Duplicates in input: Since indices (r_idx, c_idx) track position rather than value, duplicate values result in distinct pair entries as expected by the problem statement (e.g., Example 2).