Algorithm
Problem Name: 373. Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending 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]
Example 3:
Input: nums1 = [1,2], nums2 = [3], k = 3 Output: [[1,3],[2,3]] Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
Constraints:
1 <= nums1.length, nums2.length <= 105-109 <= nums1[i], nums2[i] <= 109nums1andnums2both are sorted in ascending order.1 <= k <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int** columnSizes, int* returnSize) {
int n, **p, *buff, x;
int i, j, l, r, c, *rn_on_col; // current row number on each column
*returnSize = 0;
if (k < = 0 || nums1Size == 0 || nums2Size == 0) return NULL;
n = nums1Size * nums2Size;
if (n > k) n = k;
p = malloc(n * sizeof(int *));
rn_on_col = malloc(nums2Size * sizeof(int));
// assert(p && rn_on_col);
memset(rn_on_col, -1, nums2Size * sizeof(int));
x = r = c = 0;
buff = malloc(2 * sizeof(int));
//assert(buff);
buff[0] = nums1[r];
buff[1] = nums2[c];
p[x ++] = buff;
rn_on_col[c] = r;
while (-- n) {
r = nums1Size - 1;
c = nums2Size - 1;
l = 0;
i = 1;
for (j = 0; j < nums2Size && i != 0; j ++) {
i = rn_on_col[j] + 1;
if (i < nums1Size &&
i != l &&
nums1[i] + nums2[j] < nums1[r] + nums2[c]) {
r = i; c = j;
}
l = i;
}
buff = malloc(2 * sizeof(int));
//assert(buff);
buff[0] = nums1[r];
buff[1] = nums2[c];
p[x ++] = buff;
rn_on_col[c] = r;
}
*returnSize = x;
*columnSizes = malloc(x * sizeof(int));
//assert(*columnSize);
for (i = 0; i < x; i ++) {
(*columnSizes)[i] = 2;
}
free(rn_on_col);
return p;
}
Input
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output
[[1,2],[1,4],[1,6]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto comp = [](pair < int, int>& p1, pair<int, int>& p2){ return p1.first + p1.second > p2.first + p2.second; };
priority_queue < pair<int, int>, vector<pair<int, int>>, decltype(comp)>pq(comp);
for(auto x: nums1)
for(auto y: nums2) pq.push({x, y});
vector < pair<int, int>>res;
while(k-- && !pq.empty()) res.push_back(pq.top()), pq.pop();
return res;
}
};
Input
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output
[[1,2],[1,4],[1,6]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> ans = new ArrayList<>();
if (nums1.length == 0 || nums2.length == 0 || k == 0) {
return ans;
}
PriorityQueue < Element> pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Element o1, Element o2) {
return (o1.x + o1.y) - (o2.x + o2.y);
}
});
for (int i=0; i < nums2.length && i < k; i++) {
pq.offer(new Element(0, nums2[i], nums1[0]));
}
while (k-- > 0 && !pq.isEmpty()) {
Element temp = pq.poll();
ans.add(new int[]{temp.y, temp.x});
if (temp.idx >= nums1.length-1) {
continue;
}
pq.offer(new Element(temp.idx+1, temp.x, nums1[temp.idx+1]));
}
return ans;
}
class Element {
int idx;
int x;
int y;
public Element(int val, int x, int y) {
this.idx = val;
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Element{" +
"idx=" + idx +
", x=" + x +
", y=" + y +
'}';
}
}
}
Input
nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output
[[1,1],[1,1]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const kSmallestPairs = function (nums1, nums2, k) {
const pq = new PriorityQueue((a, b) => a[0] + a[1] < b[0] + b[1])
for(let i = 0; i < nums1.length && i < k; i++) {
pq.push([nums1[i], nums2[0], 0])
}
const res = []
while(k > 0 && !pq.isEmpty()) {
const [e1, e2, e2i] = pq.pop()
res.push([e1, e2])
if(e2i + 1 < nums2.length) pq.push([e1, nums2[e2i + 1], e2i + 1])
k--
}
return res
}
class PriorityQueue {
constructor(comparator = (a, b> => a > b) {
this.heap = []
this.top = 0
this.comparator = comparator
}
size() {
return this.heap.length
}
isEmpty() {
return this.size() === 0
}
peek() {
return this.heap[this.top]
}
push(...values) {
values.forEach((value) => {
this.heap.push(value)
this.siftUp()
})
return this.size()
}
pop() {
const poppedValue = this.peek()
const bottom = this.size() - 1
if (bottom > this.top) {
this.swap(this.top, bottom)
}
this.heap.pop()
this.siftDown()
return poppedValue
}
replace(value) {
const replacedValue = this.peek()
this.heap[this.top] = value
this.siftDown()
return replacedValue
}
parent = (i) => ((i + 1) >>> 1) - 1
left = (i) => (i << 1) + 1
right = (i) => (i + 1) << 1
greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
siftUp = () => {
let node = this.size() - 1
while (node > this.top && this.greater(node, this.parent(node))) {
this.swap(node, this.parent(node))
node = this.parent(node)
}
}
siftDown = () => {
let node = this.top
while (
(this.left(node) < this.size() && this.greater(this.left(node), node)) ||
(this.right(node) < this.size() && this.greater(this.right(node), node))
) {
let maxChild =
this.right(node) < this.size() &&
this.greater(this.right(node), this.left(node))
? this.right(node)
: this.left(node)
this.swap(node, maxChild)
node = maxChild
}
}
}
Input
nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output
[[1,1],[1,1]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kSmallestPairs(self, nums1, nums2, k):
if not nums1 or not nums2: return []
n, res, cnt, heap = len(nums2), [], 0, [(nums1[i] + nums2[0], i, 0) for i in range(len(nums1))]
while heap and cnt < k:
cnt += 1
sm, i, j = heapq.heappop(heap)
res.append([nums1[i], nums2[j]])
if j + 1 < n: heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
return res
Input
nums1 = [1,2], nums2 = [3], k = 3
Output
[[1,3],[2,3]]