Find K Pairs with Smallest Sums
MedPrompt
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] <= 109nums1andnums2both are sorted in non-decreasing order.1 <= k <= 104k <= nums1.length * nums2.length
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create an empty list
allPairs. - Iterate through each element
uinnums1. - Inside this loop, iterate through each element
vinnums2. - Create a pair
(u, v)and add it toallPairs. - After generating all pairs, sort
allPairsbased on the sum of elements in each pair. - Create a result list and add the first
kpairs from the sortedallPairsto it. - Return the result list.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a max-heap
maxHeapof sizek. The heap will order pairs based on their sum in descending order. - Iterate through each element
uinnums1andvinnums2. - If
maxHeap.size() < k, add the current pair(u, v)to the heap. - If
maxHeap.size() == kand the sumu + vis 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
nums2is sorted, ifu + vis greater than or equal to the max sum in the heap, we can break the inner loop and move to the next element innums1. - After iterating through all pairs, the
maxHeapcontains theksmallest pairs. - Extract all pairs from the heap and return them.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an empty list
resultand a min-heapminHeap. 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
ifrom0tomin(nums1.length - 1, k - 1), add the index pair{i, 0}tominHeap. - Loop as long as
k > 0and the heap is not empty. - In each iteration, extract the index pair
{i, j}with the smallest sum fromminHeap. - Add the corresponding pair of values,
(nums1[i], nums2[j]), to theresultlist. - If
j+1is a valid index innums2, add the next candidate index pair{i, j+1}to the heap. - Decrement
k. - Return the
resultlist.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 ; } };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 ))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.