Find K Pairs with Smallest Sums

61.1k
0

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k, form every index-pair [firstIndex, secondIndex]. The sum of an index-pair is nums1[firstIndex] + nums2[secondIndex]. Return any k index-pairs with the smallest sums. Equal sums may appear in any order.

Example 1

Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Output: [[0, 0], [0, 1], [0, 2]]
Explanation: Index-pairs [0, 0], [0, 1], and [0, 2] produce sums 3, 5, and 7, so the three displayed index-pairs have the smallest sums.

Example 2

Input: nums1 = [1, 1], nums2 = [1], k = 2
Output: [[0, 0], [1, 0]]
Explanation: Index-pairs [0, 0] and [1, 0] are distinct, even though both index-pairs produce the value-pair [1, 1] and sum 2.

Brute Force Approach

The most direct idea forms every possible pair. After all sums become visible, sorting places the smallest pair sums at the front.

Full enumeration ignores the sorted input order, but the baseline stays easy to understand. The first k entries after sorting give the required pairs.

Algorithm

  • Begin with an empty list of pair records so every index combination can be stored with the matching sum.

  • Move through every index in nums1 and every index in nums2 because the baseline examines the full Cartesian product.

  • Compute each sum with a widened numeric type so large positive or negative values cannot overflow the comparison key.

  • Store the sum and both indices together so sorting never separates an index-pair from the matching key.

  • Sort all pair records by sum because ascending order places the globally smallest candidates first.

  • Read the first k records after sorting because every later record has an equal or larger sum.

  • Return the recorded index-pairs because every selected record already contains the required output form.

Dry Run

find-k-pairs-smallest-sums-brute-force-index-pairs.png

find-k-pairs-smallest-sums-brute-force-index-pairs.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns k pairs after complete pair sorting.
vector<vector<int>> kSmallestPairs(
vector<int>& nums1,
vector<int>& nums2,
int k
) {
// Store sum before both indices for sorting.
vector<vector<long long>> allPairs;
// Visit every index from the first array.
for (int firstIndex = 0;
firstIndex < nums1.size();
firstIndex++) {
// Pair the first index with every second index.
for (int secondIndex = 0;
secondIndex < nums2.size();
secondIndex++) {
// Use a wide type to protect the pair sum.
long long pairSum =
(long long) nums1[firstIndex]
+ nums2[secondIndex];
// Preserve the sum and matching indices.
allPairs.push_back({
pairSum,
firstIndex,
secondIndex
});
}
}
// Order every pair by ascending sum.
sort(
allPairs.begin(),
allPairs.end(),
[](vector<long long> firstPair,
vector<long long> secondPair) {
return firstPair[0] < secondPair[0];
}
);
// Keep only the first k sorted records.
vector<vector<int>> result;
for (int index = 0; index < k; index++) {
// Copy the pair indices without the sum key.
result.push_back({
(int) allPairs[index][1],
(int) allPairs[index][2]
});
}
// Return the pairs with the smallest sums.
return result;
}
};
// Driver code
int main() {
vector<int> nums1 = {1, 7, 11};
vector<int> nums2 = {2, 4, 6};
int k = 3;
Solution obj;
vector<vector<int>> result =
obj.kSmallestPairs(nums1, nums2, k);
cout << "[";
string separator = "";
for (int index = 0; index < result.size(); index++) {
cout << separator << "[" << result[index][0]
<< ", " << result[index][1] << "]";
separator = ", ";
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N log(M × N)), where M and N are the sizes of the two arrays. Generating all M × N pairs takes O(M × N) time, and sorting them takes O(M × N log(M × N)).

Space Complexity: O(M × N), because the pair-record list stores all M × N combinations, excluding the returned list.

Better Approach

Complete sorting keeps every pair, even though only k candidates matter. A max-heap of size k keeps the best candidates seen so far and exposes the largest retained sum at the root.

Every new pair enters the heap briefly. A heap larger than k loses the largest sum, so only the smallest k processed sums remain after every comparison.

Algorithm

  • Begin with an empty max-heap because the root must expose the largest sum among the retained candidates.

  • Move through every pair from nums1 and nums2 so every possible candidate receives a fair comparison.

  • Compute each pair sum with a widened numeric type so heap ordering remains correct near integer limits.

  • Push the sum and both indices together because the heap must preserve the index-pair attached to every priority.

  • Remove the heap root after the size exceeds k because the largest retained sum cannot belong to the best k candidates.

  • Pop all final heap records into a result list and reverse the list because max-heap removal produces descending sum order.

  • Return the reversed list because all unretained pairs have sums no smaller than the selected candidates.

Dry Run

find-k-pairs-smallest-sums-better-index-pairs.png

find-k-pairs-smallest-sums-better-index-pairs.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns k pairs using a bounded max-heap.
vector<vector<int>> kSmallestPairs(
vector<int>& nums1,
vector<int>& nums2,
int k
) {
// Keep the largest retained sum at the root.
priority_queue<vector<long long>> maxHeap;
// Visit every index from the first array.
for (int firstIndex = 0;
firstIndex < nums1.size();
firstIndex++) {
// Pair the first index with every second index.
for (int secondIndex = 0;
secondIndex < nums2.size();
secondIndex++) {
// Use a wide type to protect the pair sum.
long long pairSum =
(long long) nums1[firstIndex]
+ nums2[secondIndex];
// Store sum first for max-heap priority.
maxHeap.push({
pairSum,
firstIndex,
secondIndex
});
// Remove the largest sum beyond size k.
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
}
// Max-heap removal gives descending sums.
vector<vector<int>> result;
while (!maxHeap.empty()) {
vector<long long> pairData = maxHeap.top();
maxHeap.pop();
// Copy pair indices without the sum key.
result.push_back({
(int) pairData[1],
(int) pairData[2]
});
}
// Reverse descending removal into ascending order.
reverse(result.begin(), result.end());
// Return the retained smallest-sum pairs.
return result;
}
};
// Driver code
int main() {
vector<int> nums1 = {1, 7, 11};
vector<int> nums2 = {2, 4, 6};
int k = 3;
Solution obj;
vector<vector<int>> result =
obj.kSmallestPairs(nums1, nums2, k);
cout << "[";
string separator = "";
for (int index = 0; index < result.size(); index++) {
cout << separator << "[" << result[index][0]
<< ", " << result[index][1] << "]";
separator = ", ";
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N log k), where M and N are the sizes of the two arrays. All M × N pairs are processed, and each heap update takes O(log k).

Space Complexity: O(k), because the bounded heap stores at most k pair records, excluding the returned list.

Optimal Approach

The sorted arrays turn all pair sums into sorted rows. A fixed value nums1[firstIndex] paired with nums2[0], nums2[1], ... creates one non-decreasing row, so only the first unseen pair from each active row can be the next answer.

A min-heap merges the row fronts. Removing the smallest front reveals the next pair from the same row, while untouched later entries remain safely hidden behind a smaller or equal predecessor. Most of the m * n possible index-pairs never enter the heap because exploration stops after enough outputs are collected.

Algorithm

  • Begin with an empty min-heap because the smallest visible row front must become the next output pair.

  • Treat every nums1 index as a separate row because the sorted nums2 values make every row of pair sums non-decreasing.

  • Insert (firstIndex, 0) for only the first min(m, k) rows because no later row can enter the first k answers before all earlier row fronts.

  • Remove the minimum-sum record and append the matching indices because every hidden row entry has a visible predecessor with no larger sum.

  • Advance only the removed row from (firstIndex, secondIndex) to (firstIndex, secondIndex + 1), so each generated pair is inserted and removed at most once.

  • Continue until k pairs are collected because each removal fixes one next-smallest pair.

  • Return the collected list because min-heap removal produces non-decreasing pair sums.

Dry Run

find-k-pairs-smallest-sums-optimal-index-pairs

find-k-pairs-smallest-sums-optimal-index-pairs

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns k pairs by merging sorted pair rows.
vector<vector<int>> kSmallestPairs(
vector<int>& nums1,
vector<int>& nums2,
int k
) {
// Keep the smallest visible row sum at the root.
priority_queue<
vector<long long>,
vector<vector<long long>>,
greater<vector<long long>>
> minHeap;
// Limit active rows to possible answer rows.
int rowCount = min((int) nums1.size(), k);
// Seed the first pair from every active row.
for (int firstIndex = 0;
firstIndex < rowCount;
firstIndex++) {
// Use a wide type to protect the pair sum.
long long pairSum =
(long long) nums1[firstIndex]
+ nums2[0];
// Store sum and both matching indices.
minHeap.push({pairSum, firstIndex, 0});
}
// Collect pairs in non-decreasing sum order.
vector<vector<int>> result;
while (result.size() < k &&
!minHeap.empty()) {
vector<long long> pairData =
minHeap.top();
minHeap.pop();
int firstIndex = (int) pairData[1];
int secondIndex = (int) pairData[2];
// Append the smallest visible pair.
result.push_back({
firstIndex,
secondIndex
});
// Advance only a row with another pair.
if (secondIndex + 1 < nums2.size()) {
int nextSecondIndex = secondIndex + 1;
// Compute the next sum from the same row.
long long nextSum =
(long long) nums1[firstIndex]
+ nums2[nextSecondIndex];
// Expose the next unseen pair from the row.
minHeap.push({
nextSum,
firstIndex,
nextSecondIndex
});
}
}
// Return pairs already ordered by sum.
return result;
}
};
// Driver code
int main() {
vector<int> nums1 = {1, 7, 11};
vector<int> nums2 = {2, 4, 6};
int k = 3;
Solution obj;
vector<vector<int>> result =
obj.kSmallestPairs(nums1, nums2, k);
cout << "[";
string separator = "";
for (int index = 0; index < result.size(); index++) {
cout << separator << "[" << result[index][0]
<< ", " << result[index][1] << "]";
separator = ", ";
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O((R + k) log R), where R = min(M, k) and M is the size of the first array. Initializing the heap with R row-front pairs takes O(R log R), and at most k removals and replacements each take O(log R).

Space Complexity: O(R), because the min-heap stores at most one active pair for each of the R = min(M, k) rows, excluding the returned list.

Interview follow-up Questions

Yes. Different index combinations remain separate answers, even when equal array values produce the same value-pair and sum.

Heap

Read Similar Blogs

Heap

Merge K Sorted Linked Lists

Given an array lists containing the heads of k singly linked lists, merge every node into one linked list sorted in non-decreasing order. Every input list is already sorted in non-decreasing order....

92.2k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on priority, not...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflic...

57.7k
Comments0