Log inSign up
mediumLeetCodeNot Started

Find K Pairs with Smallest Sums

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k, return the k pairs (nums1[i], nums2[j]) with the smallest sums.

If total available pairs is fewer than k, return all pairs.

Example 1 · Example 1: Small Sorted Arrays:

Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Output: [[1, 2], [1, 4], [1, 6]]
Explanation: All pairs sorted by sum: [1, 2] -> sum 3 [1, 4] -> sum 5 [1, 6] -> sum 7 [7, 2] -> sum 9... The first 3 smallest pairs are [1, 2], [1, 4], [1, 6]. Min-Heap Tree (State at start): (sum 3, [1, 2]) / \ (sum 9, [7, 2]) (sum 13, [11, 2])

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model 2D Cartesian pair sums as merging K sorted linked lists.
  • Manage tuple states (sum, i, j) inside a priority queue.
  • Avoid redundant state generation without needing visited hash sets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two sorted arrays, find k smallest sum combinations.
  • Matrix of sums has sorted rows and sorted columns.
  • k is much smaller than N1 * N2 (104 vs 1010).

Algorithmic Decision Tree:

  • Generating all N1 * N2 pairs causes Memory Limit Exceeded / Time Limit Exceeded.
  • Use a Min-Heap tracking active pointers across the sorted rows.

Connected Patterns:

Merge k Sorted ListsKth Smallest Element in a Sorted MatrixK Maximum Sum Combinations

1. Brute Force — Generate All Pairs and Sort

Intuition

Compute Cartesian product of nums1 and nums2, sort all pairs ascending by their sum, and take the first k pairs.

When to apply: When N1, N2 are very small (<= 100).

Algorithm

  1. Step 1: Nested loops: for i in nums1, for j in nums2: store [i, j].
  2. Step 2: Sort all pairs based on (p[0] + p[1]).
  3. Step 3: Slice and return first min(k, total) pairs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
9 vector<vector<int>> allPairs;
10 for (int x : nums1) {
11 for (int y : nums2) {
12 allPairs.push_back({x, y});
13 }
14 }
15 sort(allPairs.begin(), allPairs.end(), [](const vector<int>& a, const vector<int>& b) {
16 return (a[0] + a[1]) < (b[0] + b[1]);
17 });
18 int count = min((int)allPairs.size(), k);
19 return vector<vector<int>>(allPairs.begin(), allPairs.begin() + count);
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> nums1 = {1, 7, 11};
26 vector<int> nums2 = {2, 4, 6};
27 auto res = sol.kSmallestPairs(nums1, nums2, 3);
28 cout << "K Smallest Pairs (Brute Force): ";
29 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N1 * N2 log(N1 * N2)) — O(N1 * N2 log(N1 * N2)) due to sorting all pairs.
  • Space complexity: O(N1 * N2) — O(N1 * N2) storage for pairs.

Why Brute Force Doesn't Scale:

For N1 = 105 and N2 = 105, N1 * N2 = 1010 pairs, requiring ~80 GB of RAM. The optimal heap uses only O(K) space (~104 items).

Runs in ~15ms for K = 10,000 versus crash/OOM for naive Cartesian product.

2. Better — Max-Heap of Size K

Intuition

Iterate through nums1 and nums2. If heap has size < k, push pair. Else if current sum is smaller than heap top, pop top and push current. If current sum > heap top and nums2 is sorted, break inner loop.

When to apply: When memory must be restricted to O(K) and early break on sorted rows is applied.

Algorithm

  1. Step 1: Initialize Max-Heap of capacity k.
  2. Step 2: For each x in nums1: for each y in nums2: sum = x + y.
  3. Step 3: If heap size < k: push (sum, [x, y]).
  4. Step 4: Else if sum < heap.top: pop and push. Else: break inner loop.
  5. Step 5: Collect and reverse elements from heap to return in ascending order.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
10 auto comp = [](const pair<int, vector<int>>& a, const pair<int, vector<int>>& b) {
11 return a.first < b.first;
12 };
13 priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, decltype(comp)> maxHeap(comp);
14
15 for (int x : nums1) {
16 for (int y : nums2) {
17 int sum = x + y;
18 if ((int)maxHeap.size() < k) {
19 maxHeap.push({sum, {x, y}});
20 } else if (sum < maxHeap.top().first) {
21 maxHeap.pop();
22 maxHeap.push({sum, {x, y}});
23 } else {
24 break;
25 }
26 }
27 }
28
29 vector<vector<int>> result;
30 while (!maxHeap.empty()) {
31 result.push_back(maxHeap.top().second);
32 maxHeap.pop();
33 }
34 reverse(result.begin(), result.end());
35 return result;
36 }
37};
38
39int main() {
40 Solution sol;
41 vector<int> nums1 = {1, 7, 11};
42 vector<int> nums2 = {2, 4, 6};
43 auto res = sol.kSmallestPairs(nums1, nums2, 3);
44 cout << "K Smallest Pairs (Max-Heap): ";
45 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(min(N1 * N2, N1 * K) log K) — O(N1 * K log K) with early exit.
  • Space complexity: O(K) — O(K) auxiliary space for heap.

3. Optimal — Min-Heap Multi-Way Merge (K Sorted Lists)

Intuition

Because both arrays are sorted, each row i is an ascending sequence. We initialize the heap with the first entry of each row. In each step, we extract the global minimum and advance that specific row pointer to j + 1. We repeat this exactly K times.

When to apply: Industry-standard optimal solution for pair selection problems.

Algorithm

  1. Step 1: If nums1 or nums2 is empty or k <= 0, return empty list.
  2. Step 2: Initialize Min-Heap with (nums1[i] + nums2[0], i, 0) for i from 0 to min(N1, k) - 1.
  3. Step 3: Repeat k times (while heap not empty):
  4. Step 4: Pop top tuple (sum, i, j). Add [nums1[i], nums2[j]] to result.
  5. Step 5: If j + 1 < nums2.length, push (nums1[i] + nums2[j + 1], i, j + 1) into heap.
  6. Step 6: Return result.

Interactive Trace for Find K Pairs with Smallest Sums

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Min-Heap initialized with first element from each row: (sum 3, [1, 2]), (sum 9, [7, 2]), (sum 13, [11, 2])
Visual state
Values and pointers at this exact step
tree
Root: (sum 3, [1, 2])
[1, 2]
Child: (sum 9, [7, 2])
[7, 2]
Child: (sum 13, [11, 2])
[11, 2]

Node order shown; add connections to display explicit tree edges.

pop: p1
Check / comparison
Top is (sum 3, [1, 2]). Pop it. Result has [[1, 2]].
Decision / next transition
Push next candidate from row 0: (nums1[0] + nums2[1] = 5, [1, 4]).
Why this step matters

Step 1: Min-Heap initialized with first element from each row: (sum 3, [1, 2]), (sum 9, [7, 2]), (sum 13, [11, 2]).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
10 vector<vector<int>> result;
11 if (nums1.empty() || nums2.empty() || k <= 0) return result;
12
13 // tuple: sum, i, j
14 using Element = tuple<int, int, int>;
15 priority_queue<Element, vector<Element>, greater<Element>> minHeap;
16
17 int limit = min((int)nums1.size(), k);
18 for (int i = 0; i < limit; i++) {
19 minHeap.push({nums1[i] + nums2[0], i, 0});
20 }
21
22 while (!minHeap.empty() && (int)result.size() < k) {
23 auto [sum, i, j] = minHeap.top();
24 minHeap.pop();
25
26 result.push_back({nums1[i], nums2[j]});
27
28 if (j + 1 < (int)nums2.size()) {
29 minHeap.push({nums1[i] + nums2[j + 1], i, j + 1});
30 }
31 }
32
33 return result;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums1 = {1, 7, 11};
40 vector<int> nums2 = {2, 4, 6};
41 auto res = sol.kSmallestPairs(nums1, nums2, 3);
42 cout << "K Smallest Pairs (Optimal): ";
43 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(K log(min(N1, K))) — O(K log(min(N1, K))) as heap holds at most min(N1, K) elements.
  • Space complexity: O(min(N1, K)) — O(min(N1, K)) auxiliary space for the Min-Heap.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Generate All Pairs & SortO(N1 * N2 log(N1 * N2))O(N1 * N2)Generate all N1 * N2 pairs, sort them ascending by sum, take first k.Storing and sorting 1010 pairs.
2.Better — Max-Heap of Size KO(N1 * N2 log K)O(K)Maintain a Max-Heap of size K. Iterate through pairs and evict larger sums.Iterating through pairs.
3.Optimal — Min-Heap Pointer Advancement (K-Way Merge)OptimalO(K log(min(N1, K)))O(min(N1, K))Initialize Min-Heap with pairs (nums1[i] + nums2[0], i, 0). Pop min and advance to (i, j + 1). Repeat K times.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Pushing both (i+1, j) and (i, j+1)

Results in duplicates unless using a visited set. The row-based initial push avoids duplicates completely.

Initializing with all N1 elements instead of min(N1, K)

When K is small (e.g. 5) and N1 is large (105), pushing 105 elements wastes time.

Integer overflow on sum

Check 64-bit integer types if numbers can be close to 109.

Crucial Edge Cases to Validate:

  • k > N1 * N2 — Returns all available pairs.
  • Single element in either array — Correctly advances the only existing row.
  • Large negative numbers — Sum comparisons handle negative numbers without underflow.
  • Duplicate values — Handled seamlessly as index advancement ensures distinct pairs.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the connection to 'Merge K Sorted Lists': each index i in nums1 acts as a sorted list of sums.
  2. Point out why pushing (i, j+1) alone avoids duplicate coordinates without a hash set.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does initializing the Min-Heap with only (nums1[i], nums2[0]) for i in [0, min(N1, K) - 1] avoid duplicate pair insertions?

Back to DSA Sheet