Leetcode•Mar 05, 2026

Find K Pairs with Smallest Sums

Hazrat Ali

Leetcode

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]

Solution
var kSmallestPairs = function(nums1, nums2, k) {
    if (nums1.length === 0 || nums2.length === 0 || k === 0) {
        return [];
    }

    const heap = [];
   
    for (let i = 0; i < Math.min(nums1.length, k); i++) {
        heap.push([nums1[i] + nums2[0], i, 0]);
    }

    const swap = (a, b) => {
        [heap[a], heap[b]] = [heap[b], heap[a]];
    };

    const heapifyUp = (index) => {
        while (index > 0) {
            let parent = Math.floor((index - 1) / 2);
            if (heap[parent][0] <= heap[index][0]) break;
            swap(parent, index);
            index = parent;
        }
    };

    const heapifyDown = (index) => {
        let size = heap.length;
        while (true) {
            let smallest = index;
            let left = 2 * index + 1;
            let right = 2 * index + 2;

            if (left < size && heap[left][0] < heap[smallest][0]) {
                smallest = left;
            }
            if (right < size && heap[right][0] < heap[smallest][0]) {
                smallest = right;
            }
            if (smallest === index) break;
            swap(index, smallest);
            index = smallest;
        }
    };

    for (let i = Math.floor(heap.length / 2); i >= 0; i--) {
        heapifyDown(i);
    }

    const result = [];

    while (k > 0 && heap.length > 0) {
        let [sum, i, j] = heap[0];
        result.push([nums1[i], nums2[j]]);

        heap[0] = heap[heap.length - 1];
        heap.pop();
        heapifyDown(0);

        if (j + 1 < nums2.length) {
            heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
            heapifyUp(heap.length - 1);
        }

        k--;
    }

    return result;
};



Comments