Find K Pairs with Smallest Sums

Difficulty: Medium
Topics: Array, Heap (Priority Queue)
Link: https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

Problem Description

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

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

Example 1:


Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:


Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Constraints:

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 and nums2 both are sorted in non-decreasing order.
1 <= k <= 104
k <= nums1.length * nums2.length

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement

Given two sorted arrays nums1 (length $m$ ) and nums2 (length $n$ ) in non-decreasing order, and an integer $k$ , we must compute the $k$ lexicographically smallest pairs $(u_i, v_j)$ where $u_i \in \text{nums1}, v_j \in \text{nums2}$ when ordered by their sum $S(u,v) = u + v$ . Formally, output a list $P$ of $k$ distinct index pairs $(i,j)$ such that the sequence of sums $S(\text{nums1}[i], \text{nums2}[j])$ is minimal and sorted non-decreasingly. If multiple pairs have the same sum, any ordering among them satisfies the problem, though typical implementations yield a deterministic order based on iteration.

Beginner-Friendly Explanation

Imagine you have two lists of numbers, each sorted from smallest to largest. You want to pick one number from the first list and one from the second list to make a pair. The “value” of a pair is just the sum of its two numbers. Your task is to find the $k$ pairs with the smallest sums. For example, if the first list is [1,7,11] and the second is [2,4,6], the pair (1,2) has sum 3, which is the smallest possible. The next smallest are (1,4) (sum 5) and (1,6) (sum 7). So for $k=3$ , you return those three pairs.

Mathematical Formulation

Let $A = [a_0, a_1, ..., a_{m-1}]$ and $B = [b_0, b_1, ..., b_{n-1}]$ be two sorted sequences ( $a_i \le a_{i+1}$ , $b_j \le b_{j+1}$ ). Define the Cartesian product $C = A \times B = \{(a_i, b_j) \mid 0 \le i < m, 0 \le j < n\}$ . Let $f: C \to \mathbb{R}$ be $f(a,b) = a + b$ . We seek the first $k$ elements of the sequence $(p_1, p_2, ..., p_{mn})$ where $\{p_i\} = C$ sorted by $f$ in non-decreasing order, i.e., $f(p_1) \le f(p_2) \le ... \le f(p_{mn})$ . If $k > mn$ , we take all $mn$ pairs. The output is the set of pairs (or a list) corresponding to the smallest $k$ sums.

Constraint Analysis

1 <= nums1.length, nums2.length <= 1e5
This immediately rules out any algorithm with complexity $O(m \times n)$ , because $10^5 \times 10^5 = 10^{10}$ , far beyond typical time limits. We need sub‑quadratic solutions, ideally $O(k \log k)$ or $O(k \log m)$ .
-1e9 <= nums1[i], nums2[i] <= 1e9
Values can be negative, zero, or positive. However, both arrays are sorted non‑decreasing, so the smallest sums will generally involve the smallest elements from both arrays. Negative values don’t break the logic, but we must ensure our algorithm doesn’t assume positivity.
nums1 and nums2 both are sorted in non-decreasing order
This is a critical structural property that allows efficient generation of pairs in increasing sum order. Without sorting, the problem would be much harder (like finding k smallest sums among all pairs from two unsorted arrays, which could be solved with a heap but with higher complexity). The sorted property enables strategies like merging or using a min‑heap on candidate frontiers.
1 <= k <= 10^4
$k$ is relatively small compared to $m \times n$ (which can be up to $10^{10}$ ). This suggests we can design an algorithm that depends more on $k$ than on $m,n$ . For example, we can explore only the first few elements of each array, because pairs involving large indices are unlikely to be among the $k$ smallest sums.
k <= nums1.length * nums2.length
Guarantees there are at least $k$ pairs, so we don’t need to handle the case where $k > m \times n$ separately (though a robust implementation might still check for early termination).
Hidden edge cases
1. Identical elements – When both arrays contain duplicates, multiple pairs can have the same sum. The output should include all required pairs, but the exact order among equal sums may not matter (as per examples). However, we must avoid duplicate pairs if indices are considered distinct? Actually, pairs are defined by values, not indices. In Example 2, [1,1] appears twice because there are two 1s in nums1 and one 1 in nums2, leading to two distinct pairs (from indices (0,0) and (1,0)). So we treat pairs as distinct based on their indices, even if values are the same.
2. All negative numbers – The smallest sum may be very negative. Our algorithm must correctly handle negative sums.
3. One very small array – If $m=1$ or $n=1$ , the problem reduces to pairing the single element of one array with the first $k$ elements of the other (or all if $k$ larger).
4. $k = 1$ – Just the pair with smallest sum, which is always (nums1[0], nums2[0]) because arrays are sorted.

2. Intuition Scaffolding

Analogies Using Problem Tags (Tags: Array, Heap (Priority Queue), Merge)

Real‑World Metaphor – Merging Sorted Lists of Distances
Imagine you are a courier company with two sorted lists: list A contains distances from your depot to customers in one city (sorted nearest to farthest), list B contains distances to customers in another city. You need to assign one driver from each city to form a team for a joint delivery. The “cost” of a team is the sum of their distances from the depot. You want the $k$ cheapest teams. Naturally, you start by pairing the nearest customers from both cities, then gradually consider slightly farther ones.
Gaming Analogy – Crafting Items with Two Resources
In a crafting game, you have two types of resources (e.g., wood and iron), each available in sorted qualities (from common to rare). Combining one wood and one iron makes a tool. The tool’s power is the sum of the qualities. You want to craft the $k$ weakest tools first (maybe to fulfill a quest). You’d start by combining the lowest‑quality wood with the lowest‑quality iron, then explore combinations that increment either resource.
Math Analogy – Exploring a Young Tableau
The matrix $M$ where $M[i][j] = \text{nums1}[i] + \text{nums2}[j]$ is a Young tableau (each row and column is sorted) because both arrays are sorted. Finding the $k$ smallest sums is equivalent to selecting the $k$ smallest entries from this matrix. This connects to algorithms for extracting elements from a sorted matrix, like using a min‑heap to perform a “k‑way merge” on the rows.

Common Pitfalls (5+ Intuitive‑but‑Wrong Approaches)

Brute‑Force All Pairs and Sort
Generating all $m \times n$ pairs, sorting by sum, and taking the first $k$ is correct but infeasible for large $m,n$ due to $O(mn \log(mn))$ time and $O(mn)$ memory.
Fix One Array, Iterate the Other
For each element in nums1, pair it with nums2[0] (the smallest), then somehow try to advance. This misses pairs like (nums1[0], nums2[1]) when nums1[1] is much larger. Example: nums1 = [1,100], nums2 = [2,3]. The second smallest sum is (1,3), not (100,2).
Two‑Pointer “Merge” as in Merging Two Sorted Lists
In classic merging of two sorted lists, we compare a[i]+b[j] with a[i+1]+b[j] and a[i]+b[j+1], but the sums are not necessarily monotonic in both directions simultaneously. A naive two‑pointer that moves the pointer with the smaller next sum can fail because the matrix is not totally ordered along diagonals. Example: nums1 = [1,2], nums2 = [3,4]. Starting at (0,0) = 4. Next candidates: (1,0)=5 and (0,1)=5. Which to pick? Both are equal, but after picking one, the other might be skipped if we only move one pointer.
Using a Heap Without Deduplication
If we push both (i+1, j) and (i, j+1) into the heap without checking if they have been visited, we risk pushing duplicates (when coming from different paths). This can cause exponential heap size. We need a visited set or a strategy to push each candidate only once.
Assuming Positive Numbers and Pruning
If we assume all numbers are positive, we could limit the search to the first $k$ elements of each array, because the sum of the $k$ ‑th smallest in nums1 and nums2 might be a bound. However, with negative numbers, the smallest sum could involve elements beyond index $k$ . Example: nums1 = [-1000, 1, 2, ..., ], nums2 = [-1000, 1, 2, ...]. The pair (-1000, -1000) is the smallest, but if we only look at first $k$ elements (say $k=1$ ), we’d miss it. So pruning must be careful.
Using Binary Search on the Sum
One might try to binary search on the sum value $S$ , count how many pairs have sum $\le S$ , and then extract the exact pairs. Counting pairs with sum $\le S$ can be done in $O(m + n)$ using two pointers (because rows are sorted). However, extracting the $k$ smallest pairs after finding the threshold is tricky because we need to output them in sorted order, and there may be many pairs with the same sum. This approach can be made to work but is more complex and less efficient for small $k$ .

3. Approach Encyclopedia

We’ll explore four strategies in increasing sophistication:

Approach 1: Brute Force (Naive Cartesian Product)

Generate all $m \times n$ pairs, compute their sums, sort by sum, and take first $k$ .

Pseudocode:

pairs = []
for i in range(len(nums1)):
    for j in range(len(nums2)):
        pairs.append( (nums1[i] + nums2[j], nums1[i], nums2[j]) )
sort pairs by first element (sum)
return first k pairs (dropping the sum)

Complexity Proof:
- Time: $O(mn \log(mn))$ for sorting. The double loop is $O(mn)$ , dominating when $mn$ large.
- Space: $O(mn)$ to store all pairs.

Visualization:

nums1 = [1,7,11], nums2 = [2,4,6]
Matrix of sums:
     2   4   6
 1   3   5   7
 7   9  11  13
11  13  15  17
All 9 pairs generated, sorted by sum: (1,2)=3, (1,4)=5, (1,6)=7, (7,2)=9, ...

Approach 2: Improved Brute Force with Bounded Heap

Instead of generating all pairs, we can use a min‑heap of size at most $k$ to keep the $k$ smallest sums seen so far. We iterate over all pairs and push into the heap, maintaining size $k$ by popping the largest when size exceeds $k$ . This avoids storing all pairs but still visits all $mn$ pairs.

Pseudocode:

import heapq
max_heap = []  # store (-sum, nums1[i], nums2[j]) for max-heap effect
for i in range(len(nums1)):
    for j in range(len(nums2)):
        s = nums1[i] + nums2[j]
        if len(max_heap) < k:
            heapq.heappush(max_heap, (-s, nums1[i], nums2[j]))
        else:
            # if current sum smaller than the largest in heap (i.e., -max_heap[0][0])
            if s < -max_heap[0][0]:
                heapq.heappushpop(max_heap, (-s, nums1[i], nums2[j]))
# after loops, max_heap contains k smallest pairs (but stored as negatives)
convert to list and sort by sum ascending

Complexity Proof:
- Time: $O(mn \log k)$ because each pair involves a heap operation of $O(\log k)$ .
- Space: $O(k)$ for the heap.
Visualization: Same matrix as before, but we only keep a heap of size $k=3$ . After processing first three pairs, heap contains [(-7,1,6), (-5,1,4), (-3,1,2)] (max at top is -3). For next pair (7,2)=9, 9 > 3, so ignore. Continue; only pairs with sum < current max (3) would replace, but none.

Approach 3: Min‑Heap with Frontier (Optimal for General k)

Leverage sorted property: the smallest pair is always (nums1[0], nums2[0]). The next smallest could be either (nums1[0], nums2[1]) or (nums1[1], nums2[0]). More generally, if we have taken pair (i,j), the next candidates are (i+1, j) and (i, j+1). We can use a min‑heap to store candidate pairs, keyed by sum. To avoid duplicates, we push (i+1, j) only when j=0 (or using a visited set). A common technique: initially push (i,0) for all i in range(min(k, m)) (or vice versa). Then repeatedly pop the smallest, and push (i, j+1) if j+1 exists.

Pseudocode (Standard Solution):

if not nums1 or not nums2: return []
heap = []
# push (nums1[i] + nums2[0], i, 0) for i in range(min(k, len(nums1)))
for i in range(min(k, len(nums1))):
    heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
result = []
while heap and len(result) < k:
    s, i, j = heapq.heappop(heap)
    result.append([nums1[i], nums2[j]])
    if j + 1 < len(nums2):
        heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))
return result

Complexity Proof:
- Time: $O(k \log k)$ because we perform at most $k$ pops and each pop may push one new candidate (so total heap operations $O(k)$ ), each $O(\log k)$ .
- Space: $O(k)$ for the heap.
Visualization: For nums1 = [1,7,11], nums2 = [2,4,6], k=3: Initial heap: [(1+2,0,0)=3, (7+2,1,0)=9, (11+2,2,0)=13]. Pop (3,0,0) → result [[1,2]]. Push (0,1): (1+4,0,1)=5 → heap now [(5,0,1), (9,1,0), (13,2,0)]. Pop (5,0,1) → result [[1,2],[1,4]]. Push (0,2): (1+6,0,2)=7 → heap [(7,0,2), (9,1,0), (13,2,0)]. Pop (7,0,2) → result [[1,2],[1,4],[1,6]]. Done.

Approach 4: Two‑Pointer / Merge with Multiple Pointers (Advanced)

This is similar to merging $m$ sorted lists, where each list corresponds to a row of the matrix: row $i$ is nums1[i] + nums2[j] for $j=0..n-1$ . Since each row is sorted, we can perform a k‑way merge using a heap of size $m$ (or $n$ ). That’s essentially Approach 3 with initializing heap with all rows. Alternatively, we can use a two‑pointer technique that moves along diagonals, but that’s more complex and not as efficient for arbitrary $k$ .

4. Code Deep Dive

We’ll annotate the optimal solution (Approach 3) line by line.

import heapq

def kSmallestPairs(nums1, nums2, k):
    """
    Return the k pairs with the smallest sums from nums1 and nums2.
    """
    # Edge case: if either array is empty, no pairs can be formed.
    if not nums1 or not nums2:
        return []
    
    # Initialize a min-heap. Each element is a tuple (sum, i, j)
    # where i is index in nums1, j is index in nums2.
    heap = []
    
    # We start by pushing pairs that combine each nums1[i] with the smallest
    # element of nums2 (nums2[0]). This ensures we have a candidate from each
    # "row" of the conceptual sum matrix.
    # However, we only need at most k such initial candidates, because we only
    # need k results. If k is smaller than len(nums1), pushing more is wasteful.
    for i in range(min(k, len(nums1))):
        # sum = nums1[i] + nums2[0], index i, index 0
        heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
    
    result = []
    
    # Continue until we have k pairs or the heap is exhausted.
    while heap and len(result) < k:
        # Pop the smallest sum pair from the heap.
        current_sum, i, j = heapq.heappop(heap)
        # Append the actual pair values to the result.
        result.append([nums1[i], nums2[j]])
        
        # If there is a next element in nums2 for the same nums1[i],
        # push the next candidate from the same row.
        if j + 1 < len(nums2):
            next_sum = nums1[i] + nums2[j + 1]
            heapq.heappush(heap, (next_sum, i, j + 1))
    
    return result

Line‑by‑Line Explanation:

if not nums1 or not nums2: – Guard against empty inputs. No pairs possible.
heap = [] – Python’s heap is a min‑heap by default. We’ll store (sum, i, j).
for i in range(min(k, len(nums1))): – We push at most k initial candidates. Why? Because the first k smallest pairs will never involve nums1[i] for i >= k if we only need k pairs? Actually, that’s not always true when there are negative numbers. However, with non‑decreasing arrays, the smallest sums will prioritize small nums1 elements. It’s safe to limit to k because any pair with i >= k will have nums1[i] >= nums1[k-1], and pairing with nums2[0] gives sum at least nums1[k-1] + nums2[0]. But there could be smaller sums from earlier i with larger j. Still, the algorithm remains correct because we only push initial candidates; we might miss some rows, but if a row i >= k could produce a sum smaller than some from rows < k, that would contradict sorting of nums1. Formal proof: The smallest element in row i is nums1[i] + nums2[0]. Since nums1 is sorted, nums1[i] + nums2[0] >= nums1[k-1] + nums2[0] for i >= k. So the first k rows already contain the smallest possible “first column” sums. Any pair (i,j) with i >= k has sum >= nums1[i] + nums2[0] >= nums1[k-1] + nums2[0]. Meanwhile, the heap initially contains all rows 0..k-1 with their first column. As we pop, we push next columns from those rows, which can be smaller than nums1[k-1]+nums2[0]. So we won’t miss any.
heapq.heappush(heap, (nums1[i] + nums2[0], i, 0)) – Push initial candidate from row i.
while heap and len(result) < k: – Main loop: we stop when we have k pairs or no more candidates.
current_sum, i, j = heapq.heappop(heap) – Extract the current smallest sum candidate.
result.append([nums1[i], nums2[j]]) – Record the pair.
if j + 1 < len(nums2): – If there is a next column in the same row, push that candidate. This ensures we explore the row incrementally.
heapq.heappush(heap, (next_sum, i, j + 1)) – Add the next candidate from row i.
return result – Return the collected pairs.

Edge Case Handling:

Example 1: Works as illustrated.
Example 2 with duplicates: nums1 = [1,1,2], nums2 = [1,2,3], k=2. Initial heap: i=0: (1+1=2,0,0), i=1: (1+1=2,1,0) (since k=2, we only push first two rows). Heap contains two entries with sum 2. First pop gives (2,0,0) → [1,1]. Push next from row 0: (1+2=3,0,1). Heap now (2,1,0), (3,0,1). Second pop gives (2,1,0) → [1,1]. Done. Correct.
k larger than m*n: The loop will stop when heap empties before we collect k pairs. But constraint says k <= m*n, so we’re safe.
Negative numbers: Works because sums are compared correctly.
One very small array: If nums1 has only 1 element, we push only one initial candidate, then keep incrementing j until we have k pairs or run out.

5. Complexity War Room

Hardware‑Aware Analysis

At $k=10^4$ , the heap contains at most $10^4$ elements. Each heap operation costs $O(\log 10^4) \approx 13$ comparisons, negligible. Memory for heap: each tuple contains two integers and a sum (Python ints are objects, but overhead is about 28 bytes each). Total ~ $10^4 \times 100$ bytes ≈ 1 MB, fits in L2/L3 cache. The algorithm is cache‑friendly because we access arrays sequentially.
For the worst‑case $m=10^5, n=10^5, k=10^4$ , we never iterate over all $mn$ pairs, only $O(k)$ operations. This is efficient.

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability (1-10)	Interview Viability	Notes
Brute Force	$O(mn \log(mn))$	$O(mn)$	9 – simple loops	❌ Fails large constraints	Only for tiny inputs
Bounded Max‑Heap	$O(mn \log k)$	$O(k)$	7 – heap logic	⚠️ May time out if $mn$ huge (1e10)	Better but still slow for max bounds
Min‑Heap Frontier	$O(k \log k)$	$O(k)$	8 – requires reasoning about rows	✅ Optimal for typical interview	Most recommended
Binary Search + Two Pointers	$O((m+n) \log \Delta + k \log k)$	$O(k)$	6 – complex counting	⚠️ Overkill, error‑prone	Useful if $k$ extremely large relative to $m,n$

$\Delta$ is the range of sums.

6. Pro Mode Extras

Variants Section

K Smallest Sums in Two Unsorted Arrays
If arrays are not sorted, we can sort them first ( $O(m \log m + n \log n)$ ) then apply the same heap method. Alternatively, use a heap with all pairs, but that’s $O(mn \log k)$ . Better to sort first.
K Smallest Sums from Three or More Arrays
Generalization to $p$ arrays: Use a min‑heap storing tuples of indices and current sum. Start with (0,0,...,0) and generate neighbors by incrementing one index at a time. Complexity $O(k \log k)$ but with higher constant due to more dimensions.
Find K Pairs with Largest Sums
Similar but use max‑heap or invert signs. Or, because arrays are sorted, the largest sums come from the ends. We can start from (m-1, n-1) and move backwards.
LeetCode 373 vs LeetCode 378 (Kth Smallest Element in a Sorted Matrix)
Problem 378 is a special case where the matrix is square and each row and column sorted. Our problem is similar but the matrix is defined as sums of two arrays, which also yields a sorted‑row‑and‑column matrix. The same heap approach works for 378.
Allow Repeated Elements (Same Index)?
If pairs could reuse the same element (like (nums1[i], nums1[i])), that’s a different problem. Not applicable here.

Interview Cheat Sheet

First Step: Clarify constraints and ask about duplicates, negative numbers, and whether $k$ can exceed $m*n$ .
Brute Force Mention: Briefly describe the naive solution to show understanding, then immediately explain why it’s inefficient.
Key Insight: “Because both arrays are sorted, the pair sums form a sorted matrix (Young tableau), so we can use a min‑heap to traverse it like merging k sorted lists.”
Initialization Trick: “We can initialize the heap with the first element of each row (or each column) to ensure we have the smallest candidate from each row.”
Complexity: Always state time and space complexity clearly. For this problem: $O(k \log k)$ time, $O(k)$ space.
Edge Cases: Mention empty arrays, $k=1$ , duplicates, negative numbers.
Testing: Walk through a small example (like given examples) to verify logic.
Optimization Note: If $k$ is very large (close to $m*n$ ), the heap size may become large, but it’s still bounded by $m$ (if we initialize with rows). In practice, $k$ is at most $10^4$ , so fine.

Final Thought: This problem is a classic example of using a heap to traverse a implicitly defined sorted structure. Mastering it prepares you for many other “k‑smallest” problems.

#373 - Find K Pairs with Smallest Sums