Find K Pairs with Smallest Sums

MEDIUM

Description

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]

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
-10⁹ <= nums1[i], nums2[i] <= 10⁹
nums1 and nums2 both are sorted in non-decreasing order.
1 <= k <= 10⁴
k <= nums1.length * nums2.length

Approaches

Checkout 3 different approaches to solve Find K Pairs with Smallest Sums. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find K Pairs with Smallest Sums. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Find K Pairs with Smallest Sums

Data Structures:

ArrayHeap (Priority Queue)

Companies:

LinkedIn |