Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Find K Pairs with Smallest Sums

Find K Pairs with Smallest Sums

Master this topic with zero to advance depth.

Find K Pairs with Smallest Sums

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 nums1 and one element from nums2.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Visual Representation

nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3 Possible Pairs: (1,2) sum=3 (1,4) sum=5 (1,6) sum=7 (7,2) sum=9 ... Smallest 3 pairs: [[1,2], [1,4], [1,6]]
Medium

Examples

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Approach 1

Level I: Brute Force + Sorting

Intuition

Generate all possible pairs from the two arrays, calculate their sums, and sort them. Return the first k pairs.

Thought Process

  1. Nest two loops to iterate over nums1 and nums2.
  2. Store each pair and its sum in a list.
  3. Sort the list by sum.
  4. Take the first k elements.
⏱ O(M * N log(M * N))💾 O(M * N)

Detailed Dry Run

nums1 = [1,2], nums2 = [3], k = 1

  1. Pairs: [[1,3] sum:4, [2,3] sum:5]
  2. Sorted: [[1,3], [2,3]]
  3. Result: [[1,3]]
java
import java.util.*;
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                res.add(Arrays.asList(nums1[i], nums2[j]));
            }
        }
        res.sort((a, b) -> (a.get(0)+a.get(1)) - (b.get(0)+b.get(1)));
        return res.size() > k ? res.subList(0, k) : res;
    }
}
Approach 2

Level II: Max-Heap of size K (Better Brute Force)

Intuition

Instead of storing all pairs and sorting, we can maintain a Max-Heap of size kk. If we find a pair smaller than the root of our Max-Heap, we replace the root. This reduces space complexity for large M,NM, N if kk is small.

Thought Process

  1. Use a Max-Heap to store [u, v] pairs based on their sum.
  2. Iterate through nums1 and nums2 (limit to kk to avoid unnecessary checks).
  3. Push each pair to the heap.
  4. If heap size exceeds kk, pop the largest (root).
  5. Return all pairs in the heap.
⏱ O(k^2 log k)💾 O(k)

Detailed Dry Run

nums1 = [1, 2], nums2 = [3], k = 1

  1. Pair [1,3], sum 4. Heap: [[1,3]]
  2. Pair [2,3], sum 5. Heap: [[2,3], [1,3]] -> Pop [2,3]. Heap: [[1,3]] Result: [[1,3]]
java
import java.util.*;
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0]+b[1]) - (a[0]+a[1]));
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                pq.offer(new int[]{nums1[i], nums2[j]});
                if (pq.size() > k) pq.poll();
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            res.add(0, Arrays.asList(p[0], p[1]));
        }
        return res;
    }
}
Approach 3

Level III: Min-Heap (Optimal)

Intuition

Since arrays are sorted, the smallest pair is (nums1[0], nums2[0]). The next candidates are (nums1[1], nums2[0]) or (nums1[0], nums2[1]). We can use a Min-Heap to explore pairs efficiently.

Thought Process

  1. Push (nums1[i], nums2[0], 0) for all i (or just i=0 and expand both ways) into a Min-Heap.
  2. In each step, pop the smallest pair (nums1[i], nums2[j]).
  3. Add it to result.
  4. Push the next potential pair (nums1[i], nums2[j+1]) into the heap.
  5. Repeat k times.
⏱ O(K log K)💾 O(K)

Detailed Dry Run

nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3

  1. Heap: [(1,2,idx_in_nums2=0)]
  2. Pop (1,2). Result: [[1,2]]. Push next in nums2: (1,4,1). Heap: [(1,4,1)]
  3. Pop (1,4). Result: [[1,2],[1,4]]. Push next: (1,6,2). Heap: [(1,6,2), (7,2,0)] (Note: 7,2 is pushed later or initialized) Actually simpler: Push all nums1[i] + nums2[0].
  4. Heap: [(1+2, 0,0), (7+2, 1,0), (11+2, 2,0)]
  5. Pop (3, 0,0). Result [[1,2]]. Push (1+4, 0,1).
  6. Pop (5, 0,1). Result [[1,2], [1,4]]. Push (1+6, 0,2).
  7. Pop (7, 0,2). Result [[1,2], [1,4], [1,6]]. Done.
java
import java.util.*;

public class Main {
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        List<List<Integer>> res = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) return res;
        
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.offer(new int[]{nums1[i], nums2[0], 0});
        }
        
        while (k-- > 0 && !pq.isEmpty()) {
            int[] curr = pq.poll();
            res.add(Arrays.asList(curr[0], curr[1]));
            if (curr[2] == nums2.length - 1) continue;
            pq.offer(new int[]{curr[0], nums2[curr[2] + 1], curr[2] + 1});
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(kSmallestPairs(new int[]{1, 7, 11}, new int[]{2, 4, 6}, 3));
    }
}
← Previous QuestionRearrange String k Distance Apart
Next Question →Sort Characters By Frequency