373. Find K Pairs with Smallest Sums LeetCode Solution
In this guide, you will get 373. Find K Pairs with Smallest Sums LeetCode Solution with the best time and space complexity. The solution to Find K Pairs with Smallest Sums problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find K Pairs with Smallest Sums
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] <= 109
nums1 and nums2 both are sorted in non-decreasing order.
1 <= k <= 104
k <= nums1.length * nums2.length
Complexity Analysis
Time Complexity: O(k\log k)
Space Complexity: O(k)
373. Find K Pairs with Smallest Sums LeetCode Solution in C++
struct T {
int i;
int j;
int sum; // nums1[i] + nums2[j]
};
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,
int k) {
vector<vector<int>> ans;
auto compare = [&](const T& a, const T& b) { return a.sum > b.sum; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
for (int i = 0; i < k && i < nums1.size(); ++i)
minHeap.emplace(i, 0, nums1[i] + nums2[0]);
while (!minHeap.empty() && ans.size() < k) {
const auto [i, j, _] = minHeap.top();
minHeap.pop();
ans.push_back({nums1[i], nums2[j]});
if (j + 1 < nums2.size())
minHeap.emplace(i, j + 1, nums1[i] + nums2[j + 1]);
}
return ans;
}
}; /* code provided by PROGIEZ */
373. Find K Pairs with Smallest Sums LeetCode Solution in Java
class T {
public int i;
public int j;
public int sum; // nums1[i] + nums2[j]
public T(int i, int j, int sum) {
this.i = i;
this.j = j;
this.sum = sum;
}
}
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>();
Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.sum, b.sum));
for (int i = 0; i < Math.min(k, nums1.length); ++i)
minHeap.offer(new T(i, 0, nums1[i] + nums2[0]));
while (!minHeap.isEmpty() && ans.size() < k) {
final int i = minHeap.peek().i;
final int j = minHeap.poll().j;
ans.add(Arrays.asList(nums1[i], nums2[j]));
if (j + 1 < nums2.length)
minHeap.offer(new T(i, j + 1, nums1[i] + nums2[j + 1]));
}
return ans;
}
} // code provided by PROGIEZ
373. Find K Pairs with Smallest Sums LeetCode Solution in Python
class Solution:
def kSmallestPairs(self, nums1: list[int],
nums2: list[int],
k: int) -> list[list[int]]:
minHeap = []
for i in range(min(k, len(nums1))):
heapq.heappush(minHeap, (nums1[i] + nums2[0], i, 0))
ans = []
while minHeap and len(ans) < k:
_, i, j = heapq.heappop(minHeap)
ans.append([nums1[i], nums2[j]])
if j + 1 < len(nums2):
heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
return ans # code by PROGIEZ
