# Find K Pairs with Smallest Sums
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-k-pairs-with-smallest-sums)
Canonical: https://scaleengineer.com/dsa/problems/find-k-pairs-with-smallest-sums
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## 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] <= 109`
* `nums1` and `nums2` both are sorted in **non-decreasing order**.
* `1 <= k <= 104`
* `k <= nums1.length * nums2.length`

# Approaches
## Brute Force by Generating All Pairs
This approach involves generating every possible pair by combining one element from `nums1` and one from `nums2`. After forming all pairs, they are sorted based on their sum in ascending order. Finally, the first `k` pairs from the sorted list are returned.
**Time:** O(N*M * log(N*M)), where N is the length of `nums1` and M is the length of `nums2`. Generating all pairs takes `O(N*M)` time. Sorting these `N*M` pairs takes `O(N*M * log(N*M))`, which dominates the complexity. · **Space:** O(N*M) to store all the generated pairs in a list, where N and M are the lengths of `nums1` and `nums2` respectively.
**Pros:** Very simple and straightforward to implement.
**Cons:** Highly inefficient for large inputs.; Will likely cause Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) errors due to creating and sorting a potentially huge list of pairs.
### Explanation
The algorithm iterates through `nums1` with a nested loop for `nums2`. In the inner loop, a pair `(nums1[i], nums2[j])` is formed and added to a list. This process continues until all `nums1.length * nums2.length` pairs are generated. The list of all pairs is then sorted using a custom comparator that compares the sums of the pairs. The sublist containing the first `k` elements is returned as the result.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> allPairs = new ArrayList<>();
        for (int u : nums1) {
            for (int v : nums2) {
                allPairs.add(Arrays.asList(u, v));
            }
        }
        
        // Sort the pairs based on their sum
        Collections.sort(allPairs, (a, b) -> (a.get(0) + a.get(1)) - (b.get(0) + b.get(1)));
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.min(k, allPairs.size()); i++) {
            result.add(allPairs.get(i));
        }
        
        return result;
    }
}
```
### Algorithm
- Create an empty list `allPairs`.
- Iterate through each element `u` in `nums1`.
- Inside this loop, iterate through each element `v` in `nums2`.
- Create a pair `(u, v)` and add it to `allPairs`.
- After generating all pairs, sort `allPairs` based on the sum of elements in each pair.
- Create a result list and add the first `k` pairs from the sorted `allPairs` to it.
- Return the result list.

## Brute Force with a Max-Heap
This approach improves upon the brute-force method by avoiding the storage and sorting of all pairs. Instead, it iterates through all possible pairs and maintains a max-heap of size `k` to keep track of the `k` smallest pairs encountered so far.
**Time:** O(N*M * log(k)), where N is `nums1.length` and M is `nums2.length`. We iterate through up to `N*M` pairs, and for each pair, we might perform a heap operation which takes `O(log k)` time. · **Space:** O(k) to store the pairs in the max-heap.
**Pros:** Significant space improvement over the full brute-force approach, using O(k) space instead of O(N*M).
**Cons:** The time complexity is still too high and will likely result in a Time Limit Exceeded (TLE) error for large inputs.
### Explanation
A max-heap (PriorityQueue in Java with a reverse order comparator) is used to store pairs. The heap is ordered by the sum of the pair's elements, with the largest sum at the top. The algorithm iterates through all `N*M` pairs. For each pair, if the heap's size is less than `k`, the pair is added. If the heap is full (size `k`), the current pair's sum is compared with the sum of the pair at the top of the heap. If the current pair's sum is smaller, the top element is removed, and the current pair is inserted. This ensures the heap always contains the `k` smallest pairs seen up to that point. After checking all pairs, the heap contains the `k` pairs with the smallest sums overall. These are extracted and returned.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> (b.get(0) + b.get(1)) - (a.get(0) + a.get(1))
        );

        for (int u : nums1) {
            for (int v : nums2) {
                if (maxHeap.size() < k) {
                    maxHeap.offer(Arrays.asList(u, v));
                } else if ((u + v) < (maxHeap.peek().get(0) + maxHeap.peek().get(1))) {
                    maxHeap.poll();
                    maxHeap.offer(Arrays.asList(u, v));
                } else {
                    // Optimization: since nums2 is sorted, if the current sum is too large,
                    // any subsequent pair in this row will also be too large.
                    break;
                }
            }
        }

        List<List<Integer>> result = new ArrayList<>(maxHeap);
        // The problem doesn't require the output to be sorted, but if it were, an extra sort would be needed.
        // Collections.sort(result, (a, b) -> (a.get(0) + a.get(1)) - (b.get(0) + b.get(1)));
        return result;
    }
}
```
### Algorithm
- Initialize a max-heap `maxHeap` of size `k`. The heap will order pairs based on their sum in descending order.
- Iterate through each element `u` in `nums1` and `v` in `nums2`.
- If `maxHeap.size() < k`, add the current pair `(u, v)` to the heap.
- If `maxHeap.size() == k` and the sum `u + v` is less than the sum of the pair at the top of the heap, remove the top element and add the current pair `(u, v)`.
- An optimization can be made: since `nums2` is sorted, if `u + v` is greater than or equal to the max sum in the heap, we can break the inner loop and move to the next element in `nums1`.
- After iterating through all pairs, the `maxHeap` contains the `k` smallest pairs.
- Extract all pairs from the heap and return them.

## Optimized Approach using a Min-Heap
This is the most efficient solution. It leverages the sorted property of the input arrays. We can visualize the sums of all pairs `(nums1[i], nums2[j])` as a sorted matrix. The problem then becomes finding the `k` smallest elements in this matrix. A min-heap is used to efficiently explore the pairs in increasing order of their sums.
**Time:** O(k * log(min(N, k))), where N is `nums1.length`. The heap is initialized with `min(N, k)` elements. Then, we perform `k` poll operations and up to `k` offer operations. The size of the heap is at most `min(N, k)`. Thus, the main loop takes `O(k * log(min(N, k)))`. · **Space:** O(min(N, k)), where N is the length of `nums1`. This space is used for the min-heap. The result list also takes O(k) space.
**Pros:** Optimal time and space complexity.; Efficiently finds the k smallest pairs without generating all possibilities.
**Cons:** The logic is more complex to understand and implement correctly compared to the brute-force approaches.
### Explanation
The core idea is that if `(nums1[i], nums2[j])` is a pair, the next smallest sum involving `nums1[i]` must be `(nums1[i], nums2[j+1])`. We use a min-heap to keep track of the next potential candidates for the smallest sum. The heap will store index pairs `(index1, index2)` to be memory efficient. Initially, we populate the heap with pairs formed from the first element of `nums2`, `nums2[0]`, with the first `k` elements of `nums1`. These pairs `(nums1[0], nums2[0]), (nums1[1], nums2[0]), ...` are the initial candidates for the smallest sums. The algorithm then proceeds in a loop for `k` iterations: extract the pair with the minimum sum from the heap, add it to the result, and then add the next candidate pair from the same row in `nums2` (if it exists) to the heap. This process guarantees that we always extract the overall minimum pair available and efficiently find the `k` smallest pairs.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) {
            return result;
        }

        // Min-heap stores arrays of {index_in_nums1, index_in_nums2}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])
        );

        // Initially, offer pairs (nums1[i], nums2[0]) for the first k elements of nums1
        for (int i = 0; i < nums1.length && i < k; i++) {
            minHeap.offer(new int[]{i, 0});
        }

        while (k-- > 0 && !minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int i = current[0];
            int j = current[1];
            
            result.add(Arrays.asList(nums1[i], nums2[j]));

            // If there's a next element in nums2 for the current element of nums1,
            // add the new pair to the heap.
            if (j + 1 < nums2.length) {
                minHeap.offer(new int[]{i, j + 1});
            }
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` and a min-heap `minHeap`. The heap will store arrays of two integers: `{index_in_nums1, index_in_nums2}`.
- The heap is ordered by the sum `nums1[index1] + nums2[index2]`.
- Add initial candidates to the heap. For each `i` from `0` to `min(nums1.length - 1, k - 1)`, add the index pair `{i, 0}` to `minHeap`.
- Loop as long as `k > 0` and the heap is not empty.
- In each iteration, extract the index pair `{i, j}` with the smallest sum from `minHeap`.
- Add the corresponding pair of values, `(nums1[i], nums2[j])`, to the `result` list.
- If `j+1` is a valid index in `nums2`, add the next candidate index pair `{i, j+1}` to the heap.
- Decrement `k`.
- Return the `result` list.

# Solutions
### Java

```java
class Solution { public List < List < Integer >> kSmallestPairs ( int [] nums1 , int [] nums2 , int k ) { PriorityQueue < int []> q = new PriorityQueue <>( Comparator . comparingInt ( a -> a [ 0 ])); for ( int i = 0 ; i < Math . min ( nums1 . length , k ); ++ i ) { q . offer ( new int [] { nums1 [ i ] + nums2 [ 0 ], i , 0 }); } List < List < Integer >> ans = new ArrayList <>(); while (! q . isEmpty () && k > 0 ) { int [] e = q . poll (); ans . add ( Arrays . asList ( nums1 [ e [ 1 ]], nums2 [ e [ 2 ]])); -- k ; if ( e [ 2 ] + 1 < nums2 . length ) { q . offer ( new int [] { nums1 [ e [ 1 ]] + nums2 [ e [ 2 ] + 1 ], e [ 1 ], e [ 2 ] + 1 }); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < vector < int >> kSmallestPairs ( vector < int >& nums1 , vector < int >& nums2 , int k ) { auto cmp = [ & nums1 , & nums2 ]( const pair < int , int >& a , const pair < int , int >& b ) { return nums1 [ a . first ] + nums2 [ a . second ] > nums1 [ b . first ] + nums2 [ b . second ]; }; int m = nums1 . size (); int n = nums2 . size (); vector < vector < int >> ans ; priority_queue < pair < int , int > , vector < pair < int , int >> , decltype ( cmp ) > pq ( cmp ); for ( int i = 0 ; i < min ( k , m ); i ++ ) pq . emplace ( i , 0 ); while ( k -- && ! pq . empty ()) { auto [ x , y ] = pq . top (); pq . pop (); ans . emplace_back ( initializer_list < int > { nums1 [ x ], nums2 [ y ]}); if ( y + 1 < n ) pq . emplace ( x , y + 1 ); } return ans ; } };
```

### Python

```python
from heapq import heapify class Solution : def kSmallestPairs ( self , nums1 : List [ int ], nums2 : List [ int ], k : int ) -> List [ List [ int ]]: ''' k could be a super large number >>> [1,2,3][:99] [1, 2, 3] ''' q = [[ u + nums2 [ 0 ], i , 0 ] for i , u in enumerate ( nums1 [: k ])] # still need '[u + nums2[0]', for q ordering heapify ( q ) ans = [] # both q and k should be checked # because k can be super larger than nums1+nums2 while q and k > 0 : _ , i , j = heappop ( q ) ans . append ([ nums1 [ i ], nums2 [ j ]]) k -= 1 if j + 1 < len ( nums2 ): heappush ( q , [ nums1 [ i ] + nums2 [ j + 1 ], i , j + 1 ]) return ans ############ import heapq class Solution ( object ): def kSmallestPairs ( self , nums1 , nums2 , k ): """ :type nums1: List[int] :type nums2: List[int] :type k: int :rtype: List[List[int]] """ if not nums1 or not nums2 : return [] heap = [( nums1 [ 0 ] + nums2 [ 0 ], 0 , 0 )] ans = [] visited = {( 0 , 0 )} while heap : val , i , j = heapq . heappop ( heap ) ans . append (( nums1 [ i ], nums2 [ j ])) k -= 1 if k == 0 : return ans if i + 1 < len ( nums1 ) and ( i + 1 , j ) not in visited : heapq . heappush ( heap , ( nums1 [ i + 1 ] + nums2 [ j ], i + 1 , j )) visited |= {( i + 1 , j )} if j + 1 < len ( nums2 ) and ( i , j + 1 ) not in visited : heapq . heappush ( heap , ( nums1 [ i ] + nums2 [ j + 1 ], i , j + 1 )) visited |= {( i , j + 1 )} return ans ############ # variation question # time complexity of O(n^2) def kth_smallest_diff ( nums , k ): # Step 1: Generate all possible pairs and calculate their differences diffs = [] nums . sort () # Sort nums first to make sure differences are calculated correctly for i in range ( len ( nums )): for j in range ( i + 1 , len ( nums )): diff = abs ( nums [ j ] - nums [ i ]) diffs . append ( diff ) # Step 2 & 3: Sort the list of differences diffs . sort () # Step 4: Return the k-th smallest difference return diffs [ k - 1 ] # Example usage nums = [ 3 , 1 , 9 ] k = 3 print ( kth_smallest_diff ( nums , k ))
```