Find K Pairs with Smallest Sums - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given two sorted integer arrays and an integer k. The task is to return the k pairs (u, v) where u comes from the first array and v from the second, such that their sums are the smallest among all possible pairs.
Approach 1: Direct Pair Generation and Sorting (Time: O(m * n log(m * n)), Space: O(m * n))
The straightforward approach generates every possible pair from the two arrays. Iterate through both arrays, compute the sum for each pair, and store the pairs in a list. Sort the list based on the pair sum and return the first k elements. This method is easy to implement and clearly demonstrates the problem logic, but it becomes expensive when both arrays are large because the number of pairs is m * n. The sorting step dominates the runtime.
Approach 2: Min-Heap (Priority Queue) Expansion (Time: O(k log m), Space: O(m))
The optimal strategy uses a min-heap (priority queue) to always expand the next smallest pair. Since both arrays are sorted, the smallest pair involving nums2 for a fixed index i in nums1 starts with (i, 0). Push the first pair from each of the first min(m, k) elements of nums1 into the heap. Each heap entry stores indices and the current sum. Repeatedly pop the smallest pair, add it to the result, and push the next pair from the same row (i, j+1). This controlled expansion ensures you only explore pairs that could belong in the smallest k, avoiding the full m * n search space. The heap guarantees that the next extracted pair always has the smallest available sum.
Recommended for interviews: Interviewers expect the min-heap solution. The brute-force generation shows you understand the problem space, but the priority queue expansion demonstrates knowledge of ordered exploration and efficient use of a heap. It reduces work from potentially millions of pairs to only the k pairs that matter.
Approach 1: Min-Heap Approach
This approach utilizes a min-heap to efficiently get the smallest sums. We initialize the heap with pairs consisting of the first element from nums1 and each element from nums2. We then extract the minimum sum from the heap, track the index of the element from nums2, and push the next pair from nums1 onto the heap. Repeat the process until we've found k pairs or exhausted possibilities.
The Python solution initializes a min-heap and then iteratively extracts the smallest elements while maintaining the heap size by considering new potential elements from the arrays. This process continues until we have the k smallest pairs.
Complexity
Time Complexity: O(k * log(min(k, n))) where n is the length of nums2.
Space Complexity: O(min(k, m*n)) used by the heap where m and n are the lengths of nums1 and nums2, respectively.
Approach 2: Direct Pair Generation and Sorting
In this naive approach, we first generate all possible pairs and their sums, storing them in a list. After generating the pairs, we sort them based on their sums and simply return the first k pairs. This approach, while straightforward, is computationally expensive for large input sizes.
In this Python example, all pairwise sums are precomputed and stored in a list, which is then sorted to extract the first k pairs. The computational cost is high due to full pair generation and sorting.
Complexity
Time Complexity: O(m * n * log(m * n)) where m and n are the lengths of nums1 and nums2, respectively.
Space Complexity: O(m * n) for storing all pairs.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: |
| Direct Pair Generation and Sorting | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Pair Generation and Sorting | O(m * n log(m * n)) | O(m * n) | Small arrays where generating all pairs is feasible and implementation simplicity matters |
| Min-Heap (Priority Queue) | O(k log m) | O(m) | Large arrays where only the smallest k pairs are needed; optimal interview solution |
Video Solution
Find K Pairs with Smallest Sums | OPTIMAL | GOOGLE | Leetcode-373 | Live Code • codestorywithMIK • 21,537 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find K Pairs with Smallest Sums easy or hard?
Find K Pairs with Smallest Sums Python/Java solution
How to solve Find K Pairs with Smallest Sums in O(k log m)?
What is the best approach for Find K Pairs with Smallest Sums?
Is Find K Pairs with Smallest Sums asked at Google/Amazon/Meta?
What data structure is used in Find K Pairs with Smallest Sums?
What is the time complexity of Find K Pairs with Smallest Sums?
Ready to solve this problem?
Practice Find K Pairs with Smallest Sums with our built-in code editor and test cases.
Practice on FleetCode