Find K Pairs with Smallest Sums solution and explanation
Google
9 more videos on this problem
Find K Pairs with Smallest Sums | OPTIMAL | GOOGLE | Leetcode-373 | Live CodecodestorywithMIK · 20:12 · 21K views
Find K Pairs with Smallest Sums - Leetcode 373 - PythonTechError · 10:01 · 18K views
Find K Pairs with Smallest Sums II Min Heap II Priority Queue II Merge k Sorted List II Leetcode 373Aryan Mittal · 23:17 · 17K views
Leetcode 373 - Find K Pairs with Smallest Sums (JAVA) UPDATED code in the descriptionLC Bear · 10:49 · 17K views
Find K Pairs with Smallest Sums | BRUTE FORCE ACCEPTED | GOOGLE | Leetcode-373 | Live CodecodestorywithMIK · 25:23 · 12K views
373. Find K Pairs with Smallest Sums | Min-Heap | LeetCode Daily ChallengeDeep Tech · 19:49 · 7K views
LeetCode 373 Find K Pairs with Smallest SumsJeevan Kumar - Cracckify · 10:41 · 5K views
Leetcode--373 find k pairs with smallest sums (Heap)You Wu · 18:36 · 4K views
Find K Pairs with Smallest Sums - LeetCode 373 - PythonAlpha-Code · 18:44 · 3K views
373. Find K Pairs with Smallest Sums | Leetcode | Medium | Java | Priority QueueAlgorithmHQ · 21:17 · 3K views
The problem
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] <= 109nums1andnums2both are sorted in non-decreasing order.1 <= k <= 104k <= nums1.length * nums2.length
Approach overview
Problem Overview: You are given two sorted integer arrays and an integer k. The task is to return the k pairs (u, v) where u comes from the first array and v from the second, such that their sums are the smallest among all possible pairs.
Approach 1: Direct Pair Generation and Sorting (Time: O(m * n log(m * n)), Space: O(m * n))
The straightforward approach generates every possible pair from the two arrays. Iterate through both arrays, compute the sum for each pair, and store the pairs in a list. Sort the list based on the pair sum and return the first k elements. This method is easy to implement and clearly demonstrates the problem logic, but it becomes expensive when both arrays are large because the number of pairs is m * n. The sorting step dominates the runtime.
Approach 2: Min-Heap (Priority Queue) Expansion (Time: O(k log m), Space: O(m))
The optimal strategy uses a min-heap (priority queue) to always expand the next smallest pair. Since both arrays are sorted, the smallest pair involving nums2 for a fixed index i in nums1 starts with (i, 0). Push the first pair from each of the first min(m, k) elements of nums1 into the heap. Each heap entry stores indices and the current sum. Repeatedly pop the smallest pair, add it to the result, and push the next pair from the same row (i, j+1). This controlled expansion ensures you only explore pairs that could belong in the smallest k, avoiding the full m * n search space. The heap guarantees that the next extracted pair always has the smallest available sum.
Recommended for interviews: Interviewers expect the min-heap solution. The brute-force generation shows you understand the problem space, but the priority queue expansion demonstrates knowledge of ordered exploration and efficient use of a heap. It reduces work from potentially millions of pairs to only the k pairs that matter.
Approach 1: Min-Heap Approach
This approach utilizes a min-heap to efficiently get the smallest sums. We initialize the heap with pairs consisting of the first element from nums1 and each element from nums2. We then extract the minimum sum from the heap, track the index of the element from nums2, and push the next pair from nums1 onto the heap. Repeat the process until we've found k pairs or exhausted possibilities.
import heapq
def kSmallestPairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
min_heap = []
for j in range(min(k, len(nums2))): # Ensure we do not exceed possible pairs
heapq.heappush(min_heap, (nums1[0] + nums2[j], 0, j))
result = []
while k > 0 and min_heap:
sum, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])
if i + 1 < len(nums1):
heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))
k -= 1
return resultimport java.util.*;
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> result = new ArrayList<>();
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int j = 0; j < Math.min(k, nums2.length); j++) {
minHeap.offer(new int[] {nums1[0] + nums2[j], 0, j});
}
while (k > 0 && !minHeap.isEmpty()) {
int[] cur = minHeap.poll();
result.add(Arrays.asList(nums1[cur[1]], nums2[cur[2]]));
if (cur[1] + 1 < nums1.length) {
minHeap.offer(new int[] {nums1[cur[1] + 1] + nums2[cur[2]], cur[1] + 1, cur[2]});
}
k--;
}
return result;
}
}#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> minHeap;
vector<vector<int>> result;
for (int j = 0; j < min(k, static_cast<int>(nums2.size())); j++) {
minHeap.push({nums1[0] + nums2[j], {0, j}});
}
while (k-- > 0 && !minHeap.empty()) {
auto current = minHeap.top();
minHeap.pop();
int i = current.second.first;
int j = current.second.second;
result.push_back({nums1[i], nums2[j]});
if (i + 1 < nums1.size()) {
minHeap.push({nums1[i + 1] + nums2[j], {i + 1, j}});
}
}
return result;
}var kSmallestPairs = function(nums1, nums2, k) {
const minHeap = new MinPriorityQueue({ priority: x => x.sum });
const result = [];
for (let j = 0; j < Math.min(k, nums2.length); j++) {
minHeap.enqueue({ sum: nums1[0] + nums2[j], i: 0, j: j });
}
while (k > 0 && !minHeap.isEmpty()) {
let { sum, i, j } = minHeap.dequeue().element;
result.push([nums1[i], nums2[j]]);
if (i + 1 < nums1.length) {
minHeap.enqueue({ sum: nums1[i + 1] + nums2[j], i: i + 1, j: j });
}
k--;
}
return result;
};#include <stdio.h>
#include <stdlib.h>
typedef struct {
int sum;
int i;
int j;
} Pair;
int compare(const void* a, const void* b) {
return ((Pair*)a)->sum - ((Pair*)b)->sum;
}
Pair* create_pair(int sum, int i, int j) {
Pair* p = (Pair*)malloc(sizeof(Pair));
p->sum = sum;
p->i = i;
p->j = j;
return p;
}
void add_to_heap(Pair** heap, int* size, int capacity, int sum, int i, int j) {
if (*size < capacity) {
heap[*size] = create_pair(sum, i, j);
qsort(heap, *size + 1, sizeof(Pair*), compare);
(*size)++;
}
}
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
Pair** heap = (Pair**)malloc(k * sizeof(Pair*));
int heapSize = 0;
for (int j = 0; j < nums2Size && j < k; j++)
add_to_heap(heap, &heapSize, k, nums1[0] + nums2[j], 0, j);
int** result = (int**)malloc(k * sizeof(int*));
*returnColumnSizes = (int*)malloc(k * sizeof(int));
while (*returnSize < k && heapSize > 0) {
Pair* smallest = heap[0];
result[*returnSize] = (int*)malloc(2 * sizeof(int));
(*returnColumnSizes)[*returnSize] = 2;
result[*returnSize][0] = nums1[smallest->i];
result[*returnSize][1] = nums2[smallest->j];
(*returnSize)++;
heap[0] = heap[heapSize - 1];
heapSize--;
qsort(heap, heapSize, sizeof(Pair*), compare);
if (smallest->i + 1 < nums1Size)
add_to_heap(heap, &heapSize, k, nums1[smallest->i + 1] + nums2[smallest->j], smallest->i + 1, smallest->j);
free(smallest);
}
free(heap);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> KSmallestPairs(int[] nums1, int[] nums2, int k) {
var minHeap = new SortedSet<(int sum,int i, int j)>();
var result = new List<IList<int>>();
for (int j = 0; j < Math.Min(k, nums2.Length); j++) {
minHeap.Add((nums1[0] + nums2[j], 0, j));
}
while (k-- > 0 && minHeap.Count > 0) {
var current = minHeap.Min;
minHeap.Remove(current);
int i = current.i;
int j = current.j;
result.Add(new List<int>{ nums1[i], nums2[j] });
if (i + 1 < nums1.Length) {
minHeap.Add((nums1[i + 1] + nums2[j], i + 1, j));
}
}
return result;
}
}The Python solution initializes a min-heap and then iteratively extracts the smallest elements while maintaining the heap size by considering new potential elements from the arrays. This process continues until we have the k smallest pairs.
Time Complexity: O(k * log(min(k, n))) where n is the length of nums2.
Space Complexity: O(min(k, m*n)) used by the heap where m and n are the lengths of nums1 and nums2, respectively.
Approach 2: Direct Pair Generation and Sorting
In this naive approach, we first generate all possible pairs and their sums, storing them in a list. After generating the pairs, we sort them based on their sums and simply return the first k pairs. This approach, while straightforward, is computationally expensive for large input sizes.
def kSmallestPairs(nums1, nums2, k):
pairs = []
for i in nums1:
for j in nums2:
pairs.append((i + j, [i, j]))
pairs.sort(key=lambda x: x[0])
return [pair[1] for pair in pairs[:k]]import java.util.*;
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> pairs = new ArrayList<>();
for (int num1 : nums1) {
for (int num2 : nums2) {
pairs.add(new int[] {num1 + num2, num1, num2});
}
}
pairs.sort((a, b) -> Integer.compare(a[0], b[0]));
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < Math.min(k, pairs.size()); i++) {
result.add(Arrays.asList(pairs.get(i)[1], pairs.get(i)[2]));
}
return result;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int, pair<int, int>>> pairs;
for (int i = 0; i < nums1.size(); ++i) {
for (int j = 0; j < nums2.size(); ++j) {
pairs.push_back({nums1[i] + nums2[j], {nums1[i], nums2[j]}});
}
}
sort(pairs.begin(), pairs.end());
vector<vector<int>> result;
for (int i = 0; i < min(k, (int)pairs.size()); ++i) {
result.push_back({pairs[i].second.first, pairs[i].second.second});
}
return result;
}var kSmallestPairs = function(nums1, nums2, k) {
let pairs = [];
for (let i = 0; i < nums1.length; i++) {
for (let j = 0; j < nums2.length; j++) {
pairs.push([nums1[i] + nums2[j], nums1[i], nums2[j]]);
}
}
pairs.sort((a, b) => a[0] - b[0]);
let result = [];
for (let i = 0; i < Math.min(k, pairs.length); i++) {
result.push([pairs[i][1], pairs[i][2]]);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
struct Pair {
int sum;
int num1;
int num2;
};
int compare(const void* a, const void* b) {
return ((struct Pair*)a)->sum - ((struct Pair*)b)->sum;
}
void add_pair(struct Pair* pairs, int* index, int n1, int n2) {
struct Pair pair;
pair.sum = n1 + n2;
pair.num1 = n1;
pair.num2 = n2;
pairs[*index] = pair;
(*index)++;
}
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes) {
struct Pair* pairs = (struct Pair*)malloc(nums1Size * nums2Size * sizeof(struct Pair));
int pairCount = 0;
for (int i = 0; i < nums1Size; ++i) {
for (int j = 0; j < nums2Size; ++j) {
add_pair(pairs, &pairCount, nums1[i], nums2[j]);
}
}
qsort(pairs, pairCount, sizeof(struct Pair), compare);
int** result = (int**)malloc(k * sizeof(int*));
*returnColumnSizes = (int*)malloc(k * sizeof(int));
*returnSize = 0;
for (int i = 0; i < k && i < pairCount; ++i) {
result[i] = (int*)malloc(2 * sizeof(int));
(*returnColumnSizes)[i] = 2;
result[i][0] = pairs[i].num1;
result[i][1] = pairs[i].num2;
(*returnSize)++;
}
free(pairs);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> KSmallestPairs(int[] nums1, int[] nums2, int k) {
var pairs = new List<(int sum, int num1, int num2)>();
for (int i = 0; i < nums1.Length; i++) {
for (int j = 0; j < nums2.Length; j++) {
pairs.Add((nums1[i] + nums2[j], nums1[i], nums2[j]));
}
}
pairs.Sort((a, b) => a.sum.CompareTo(b.sum));
var result = new List<IList<int>>();
for (int i = 0; i < Math.Min(k, pairs.Count); i++) {
result.Add(new List<int> { pairs[i].num1, pairs[i].num2 });
}
return result;
}
}In this Python example, all pairwise sums are precomputed and stored in a list, which is then sorted to extract the first k pairs. The computational cost is high due to full pair generation and sorting.
Time Complexity: O(m * n * log(m * n)) where m and n are the lengths of nums1 and nums2, respectively.
Space Complexity: O(m * n) for storing all pairs.
Approach 3: Default Approach
func kSmallestPairs(nums1, nums2 []int, k int) (ans [][]int) {
m, n := len(nums1), len(nums2)
h := hp{nil, nums1, nums2}
for i := 0; i < k && i < m; i++ {
h.data = append(h.data, pair{i, 0})
}
for h.Len() > 0 && len(ans) < k {
p := heap.Pop(&h).(pair)
i, j := p.i, p.j
ans = append(ans, []int{nums1[i], nums2[j]})
if j+1 < n {
heap.Push(&h, pair{i, j + 1})
}
}
return
}
type pair struct{ i, j int }
type hp struct {
data []pair
nums1, nums2 []int
}
func (h hp) Len() int { return len(h.data) }
func (h hp) Less(i, j int) bool {
a, b := h.data[i], h.data[j]
return h.nums1[a.i]+h.nums2[a.j] < h.nums1[b.i]+h.nums2[b.j]
}
func (h hp) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *hp) Push(v any) { h.data = append(h.data, v.(pair)) }
func (h *hp) Pop() any { a := h.data; v := a[len(a)-1]; h.data = a[:len(a)-1]; return v }Complexity comparison
| Approach | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: |
| Direct Pair Generation and Sorting | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Pair Generation and Sorting | O(m * n log(m * n)) | O(m * n) | Small arrays where generating all pairs is feasible and implementation simplicity matters |
| Min-Heap (Priority Queue) | O(k log m) | O(m) | Large arrays where only the smallest k pairs are needed; optimal interview solution |
Frequently asked questions
Is Find K Pairs with Smallest Sums easy or hard?
Find K Pairs with Smallest Sums is rated Medium difficulty. The challenge is recognizing that generating all m*n pairs is unnecessary and that a min-heap can expand only the next smallest candidates. Once the heap strategy is understood, the implementation becomes straightforward.
Find K Pairs with Smallest Sums Python/Java solution
Most implementations push index pairs into a priority queue and compute sums using the original arrays. Python uses heapq, Java uses PriorityQueue, and C++ typically uses priority_queue with a custom comparator. The algorithm structure remains the same across languages with O(k log m) complexity.
How to solve Find K Pairs with Smallest Sums in O(k log m)?
Use a min-heap that stores indices (i, j) representing the pair nums1[i] + nums2[j]. Start by pushing (i, 0) for i from 0 to min(m, k)-1. Each time you pop the smallest pair, append it to the result and push the next pair (i, j+1) if it exists. This expands candidates in increasing sum order while limiting work to k pairs.
What is the best approach for Find K Pairs with Smallest Sums?
The min-heap (priority queue) approach is the most efficient. Initialize the heap with pairs combining the first element of nums2 with the first min(m, k) elements of nums1, then repeatedly pop the smallest pair and push the next candidate from the same row. This generates pairs in sorted order without exploring all combinations, giving O(k log m) time complexity.
Is Find K Pairs with Smallest Sums asked at Google/Amazon/Meta?
This problem appears in interviews at companies that test heap and priority queue usage, including Amazon and Google-style interview rounds. It evaluates your ability to combine sorted arrays with a min-heap to efficiently explore the smallest combinations.
What data structure is used in Find K Pairs with Smallest Sums?
The key data structure is a min-heap (priority queue). It keeps track of the next smallest pair sum while allowing efficient insertion and removal in O(log n). Arrays are also used to access elements by index when expanding candidate pairs.
What is the time complexity of Find K Pairs with Smallest Sums?
The optimal heap-based solution runs in O(k log m) time, where m is the length of nums1. Each of the k results requires a heap pop and possibly a push, both costing O(log m). A brute-force method that generates all pairs and sorts them takes O(m * n log(m * n)).