Last updated on July 20th, 2024 at 04:09 am

Here, We see Find K Pairs with Smallest Sums LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Heap

Companies

Google, Uber

Level of Question

Medium

Find K Pairs with Smallest Sums LeetCode Solution

Problem Statement

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 (u₁, v₁), (u₂, v₂), …, (u_k, v_k) 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]

1. Find K Pairs with Smallest Sums LeetCode Solution C++

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> resV;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for(int x : nums1) {
            pq.push({x + nums2[0], 0});
        }
        while(k-- && !pq.empty()) {
            int sum = pq.top().first;
            int pos = pq.top().second;
            resV.push_back({sum - nums2[pos], nums2[pos]});
            pq.pop();
            if(pos + 1 < nums2.size()) {
                pq.push({sum - nums2[pos] + nums2[pos + 1], pos + 1});
            }
        }
        return resV;
    }
};

2. Find K Pairs with Smallest Sums Leetcode Solution Java

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> resV = new ArrayList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int x : nums1) {
            pq.offer(new int[]{x + nums2[0], 0});
        }
        while (k > 0 && !pq.isEmpty()) {
            int[] pair = pq.poll();
            int sum = pair[0];
            int pos = pair[1];
            List<Integer> currentPair = new ArrayList<>();
            currentPair.add(sum - nums2[pos]);
            currentPair.add(nums2[pos]);
            resV.add(currentPair);
            if (pos + 1 < nums2.length) {
                pq.offer(new int[]{sum - nums2[pos] + nums2[pos + 1], pos + 1});
            }
            k--;
        }
        return resV;
    }
}

3. Find K Pairs with Smallest Sums Solution JavaScript

var kSmallestPairs = function(nums1, nums2, k) {
    const minHeap = new MinPriorityQueue({ priority: x => x[0] });
    for (let i = 0; i < nums1.length; i++) {
        const num1 = nums1[i];
        const num2 = nums2[0];
        minHeap.enqueue([num1 + num2, i, 0]);
    }
    const n = nums2.length;
    const res = [];
    while (k > 0 && !minHeap.isEmpty()) {
        const [sum, idx1, idx2] = minHeap.dequeue().element;
        res.push([nums1[idx1], nums2[idx2]]);
        if (res.length === k) return res;
        if (idx2 < n - 1) {
            minHeap.enqueue([nums1[idx1] + nums2[idx2 + 1], idx1, idx2 + 1]);
        } 
    }
    return res;
};

4. Find K Pairs with Smallest Sums Solution Python

class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        resV = []
        pq = []
        for x in nums1:
            heapq.heappush(pq, [x + nums2[0], 0])
        while k > 0 and pq:
            pair = heapq.heappop(pq)
            s, pos = pair[0], pair[1]
            resV.append([s - nums2[pos], nums2[pos]])
            if pos + 1 < len(nums2):
                heapq.heappush(pq, [s - nums2[pos] + nums2[pos + 1], pos + 1])
            k -= 1
        return resV