Sponsored
Sponsored
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.
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.
1import heapq
2
3def kSmallestPairs(nums1, nums2, k):
4 if not nums1 or not nums2:
5 return []
6 min_heap = []
7 for j in range(min(k, len(nums2))): # Ensure we do not exceed possible pairs
8 heapq.heappush(min_heap, (nums1[0] + nums2[j], 0, j))
9
10 result = []
11 while k > 0 and min_heap:
12 sum, i, j = heapq.heappop(min_heap)
13 result.append([nums1[i], nums2[j]])
14 if i + 1 < len(nums1):
15 heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))
16 k -= 1
17 return resultThe 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.
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.
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.
1using System.Collections.Generic;
public class Solution {
public IList<IList<int>> KSmallestPairs(int[] nums1, int[] nums2, int k) {
var pairs = new List<(int sum, int num1, int num2)>();
for (int i = 0; i < nums1.Length; i++) {
for (int j = 0; j < nums2.Length; j++) {
pairs.Add((nums1[i] + nums2[j], nums1[i], nums2[j]));
}
}
pairs.Sort((a, b) => a.sum.CompareTo(b.sum));
var result = new List<IList<int>>();
for (int i = 0; i < Math.Min(k, pairs.Count); i++) {
result.Add(new List<int> { pairs[i].num1, pairs[i].num2 });
}
return result;
}
}C# implementation uses tuples and simple sorting to derive the top k pairs after comprehensive pair list generation. Simple and illustrative but computationally intensive.