leetcode

commit d48e9be6397b54369e7ce10048ae9c3952c87500
parent bf93593e129152e442cf33535fa4342d81f3eb43
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 14 Aug 2024 20:41:48 +0200

Daily Problem

Diffstat:
A
Problems/0719.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 32 insertions(+), 0 deletions(-)
diff --git a/Problems/0719.cpp b/Problems/0719.cpp
@@ -0,0 +1,31 @@
+class Solution {
+    int count(const vector<int> &nums, int tgt) const {
+        int res = 0;
+
+        for (int l = 0, r = 1; r < size(nums); r++) {
+            while (nums[r] - nums[l] > tgt)
+                l++;
+            res += r - l;
+        }
+
+        return res;
+    }
+
+  public:
+    int smallestDistancePair(vector<int> &nums, int k) const {
+        sort(begin(nums), end(nums));
+
+        int low = 0, high = nums.back() - nums.front();
+        while (low < high) {
+            const int mid = low + (high - low) / 2;
+            const int cnt = count(nums, mid);
+
+            if (cnt < k)
+                low = mid + 1;
+            else
+                high = mid;
+        }
+
+        return low;
+    }
+};
diff --git a/README.md b/README.md
@@ -473,6 +473,7 @@ for solving problems.
 |  0712  |   Medium   | [Minimum ASCII Delete Sum for Two Strings](Problems/0712.cpp)                                      |
 |  0713  |   Medium   | [Subarray Product Less Than K](Problems/0713.cpp)                                                  |
 |  0714  |   Medium   | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp)                          |
+|  0719  |    Hard    | [Find K-th Smallest Pair Distance](Problems/0719.cpp)                                              |
 |  0720  |   Medium   | [Longest Word in Dictionary](Problems/0720.cpp)                                                    |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                              |
 |  0725  |   Medium   | [Split Linked List in Parts](Problems/0725.cpp)                                                    |