grid47 Exploring patterns and algorithms
Sep 30, 2024
6 min read
Solution to LeetCode 373: Find K Pairs with Smallest Sums Problem
Given two sorted integer arrays nums1 and nums2 and an integer k, return the k pairs with the smallest sums. Each pair consists of one element from nums1 and one element from nums2.
Problem
Approach
Steps
Complexity
Input: The input consists of two sorted arrays, `nums1` and `nums2`, and an integer `k`.
A min-heap (priority queue) `pq` is initialized, which will store vectors containing the sum of pairs and the corresponding elements from `nums1` and `nums2`.
5 : Loop Iteration
for(int i =0; i < n1 && i < k; i++) {
This loop iterates over `nums1` and adds the first element of each pair from `nums1[i]` and `nums2[0]` into the priority queue.
The sum of `nums1[i]` and `nums2[0]` is pushed into the priority queue along with the corresponding elements and the index `0` (representing the first element of `nums2`).
7 : Loop Condition
while(!pq.empty() && ans.size() < k) {
The while loop continues as long as there are elements in the priority queue and the number of pairs found is less than `k`.
8 : Priority Queue Pop
auto it = pq.top();
The smallest sum pair is popped from the priority queue.
9 : Priority Queue Pop
pq.pop();
The smallest element is removed from the priority queue after it has been retrieved.
10 : Answer Update
ans.push_back({it[1], it[2]});
The pair `it[1]` and `it[2]` (the elements from `nums1` and `nums2`) is added to the result `ans`.
11 : Condition Check
if(it[3] == n2 -1) continue;
If the index `it[3]` has reached the last element of `nums2`, the loop continues to the next iteration without making any changes, as no further pairs are available from `nums2` for this particular element of `nums1`.
12 : Element Update
it[0] = it[1] + nums2[it[3] +1];
The sum of `it[1]` (current element of `nums1`) and the next element of `nums2` is updated in the vector.
13 : Element Update
it[2] = nums2[it[3] +1];
The next element of `nums2` is updated in the vector `it`.
14 : Index Update
it[3] = it[3] +1;
The index `it[3]` is incremented to reflect the movement to the next element of `nums2`.
15 : Priority Queue Push
pq.push(it);
The updated vector is pushed back into the priority queue to continue processing.
16 : Return Statement
return ans;
The result `ans`, containing the k smallest pairs, is returned.
Best Case: O(k log k)
Average Case: O(k log k)
Worst Case: O(k log n2)
Description: In the worst case, we push and pop from the priority queue for `k` pairs, each involving logarithmic operations in relation to the size of the second array `nums2`.
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is determined by the storage used for the priority queue and the resulting pairs.
