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.
- is relatively small () compared to potential pair counts (up to , where lengths can be up to ).
- Values can be negative, but since arrays are sorted, the relative order holds regardless of sign.
Implicit edge cases:
- What if
kis 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 , calculate sums, sort them, and slice the first .
- Time Complexity: due to sorting all pairs. With lengths up to , this is roughly operations, which will Time Limit Exceed (TLE).
- We need a way to avoid generating the full matrix of sums.
Since both arrays are sorted:
- The smallest sum must involve
nums2[0]combined with some element fromnums1. - If we pick
(u, v)as our current best pair in row (where row corresponds to index innums1), the next candidate for that specific row is simply . - We can visualize this as a matrix where rows are indices of
nums1and columns are indices ofnums2. 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.
- Initialization: We start with
nums2[0]paired against every element innums1. However, to keep complexity low relative to , we only initialize the heap for indices ofnums1up to . Why? Because even if there are more rows than needed, they can’t contribute to top- sums before their first element is processed. - Heap Structure: Each entry in the heap will be a tuple:
(sum_val, index_in_nums1, index_in_nums2). Python’sheapqsorts tuples lexicographically, so it naturally orders by sum first. - Expansion Loop: We run exactly 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.
- Pop the smallest element
- Termination: If we run out of pairs before reaching iterations (because
k > total_pairs), stop and return what we found.
Complexity Analysis
- Time Complexity: . We perform at most heap operations (pop + push). The heap size is bounded by , which effectively keeps the log factor small relative to total pairs. Initialization takes .
- Space Complexity: 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
- : The loop condition
len(result) < k and heapensures we stop when the heap is empty (all combinations exhausted), returning all available valid pairs. - Small arrays / Large : Logic handles cases where total possible pairs are fewer than requested .
- 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).