leetcode

commit 5a4fc68ffcfbea836515b38a1dc3c28b3eb2485c
parent 11545c37d7846e87a2fffced3b271256bd672e5f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 11 Dec 2024 15:11:25 +0100

Daily Problem

Diffstat:
A
Problems/2779.cpp
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/2779.cpp b/Problems/2779.cpp
@@ -0,0 +1,44 @@
+// Binary search: O(n * logn)
+class Solution {
+  public:
+    int maximumBeauty(vector<int> &nums, int k) const {
+        sort(begin(nums), end(nums));
+        int res = 1;
+
+        for (int i = 0; i < size(nums); i++) {
+            const auto it = upper_bound(begin(nums), end(nums), 2 * k + nums[i]);
+            res = max(res, (int)distance(begin(nums) + i, it));
+        }
+
+        return res;
+    }
+};
+
+// Line sweep: O(n)
+class Solution {
+  public:
+    int maximumBeauty(const vector<int> &nums, int k) const {
+        int mini = INT_MAX, maxi = INT_MIN;
+        static int count[200002];
+
+        memset(count, 0x00, sizeof(count));
+        for (const int n : nums) {
+            const int a = max(n - k, 0);
+            const int b = n + k + 1;
+
+            count[a]++;
+            count[b]--;
+
+            mini = min(mini, a);
+            maxi = max(maxi, b);
+        }
+
+        int res = 1;
+        for (int i = mini, acc = 0; i <= maxi; i++) {
+            acc += count[i];
+            res = max(res, acc);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1414,6 +1414,7 @@ reference and a base for solving problems.
 |  2766  |   Medium   | [Relocate Marbles](Problems/2766.cpp)                                                              |
 |  2767  |   Medium   | [Partition String Into Minimum Beautiful Substrings](Problems/2767.cpp)                            |
 |  2769  |    Easy    | [Find the Maximum Achievable Number](Problems/2769.cpp)                                            |
+|  2779  |   Medium   | [Maximum Beauty of an Array After Applying Operation](Problems/2779.cpp)                           |
 |  2780  |   Medium   | [Minimum Index of a Valid Split](Problems/2780.cpp)                                                |
 |  2785  |   Medium   | [Sort Vowels in a String](Problems/2785.cpp)                                                       |
 |  2799  |   Medium   | [Count Complete Subarrays in an Array](Problems/2799.cpp)                                          |