leetcode

commit 3d9ab29390f6b2dc09a7c2a1c5a41f1964176289
parent 1197f072a64c080f70d6ad2321cee06d83938de2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 27 Jun 2023 20:54:48 +0200

Daily Problem

Diffstat:
A
Problems/0373.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/0373.cpp b/Problems/0373.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  typedef tuple<int, int, int> tpl;
+
+public:
+  vector<vector<int>> kSmallestPairs(const vector<int> &nums1,
+                                     const vector<int> &nums2, int k) {
+    priority_queue<tpl, vector<tpl>, greater<tpl>> pq;
+    vector<vector<int>> res;
+    res.reserve(k);
+
+    for (int i = 0; i < min(k, (int)nums1.size()); i++)
+      pq.push({nums1[i] + nums2[0], i, 0});
+
+    while (k-- && !pq.empty()) {
+      auto [sum, i, j] = pq.top();
+      pq.pop();
+      res.push_back({nums1[i], nums2[j]});
+      if (j == nums2.size() - 1) continue;
+      pq.push({nums1[i] + nums2[j + 1], i, j + 1});
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -243,6 +243,7 @@ for solving problems.
 |  0352  |    Hard    | [Data Stream as Disjoint Intervals](Problems/0352.cpp)                                           |
 |  0367  |    Easy    | [Valid Perfect Square](Problems/0367.cpp)                                                        |
 |  0371  |   Medium   | [Sum of Two Integers](Problems/0371.cpp)                                                         |
+|  0373  |   Medium   | [Find K Pairs with Smallest Sums](Problems/0373.cpp)                                             |
 |  0374  |    Easy    | [Guess Number Higher or Lower](Problems/0374.cpp)                                                |
 |  0376  |   Medium   | [Wiggle Subsequence](Problems/0376.cpp)                                                          |
 |  0377  |   Medium   | [Combination Sum IV](Problems/0377.cpp)                                                          |