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] <= 109nums1 and nums2 both are sorted in non-decreasing order.1 <= k <= 104k <= nums1.length * nums2.lengthThis 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.
Java
C++
C
C#
JavaScript
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.
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.
Java
C++
C
C#
JavaScript
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 | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: |
| Direct Pair Generation and Sorting | Time Complexity: |
Find K-th Smallest Pair Distance - Leetcode 719 - Python • NeetCodeIO • 17,861 views views
Watch 9 more video solutions →Practice Find K Pairs with Smallest Sums with our built-in code editor and test cases.
Practice on FleetCode