leetcode

commit e12dcc224c11a4be2b290d84e7cbc89826a28a13
parent 295259ef940d3588a7933f524438680fab828f61
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 30 Oct 2024 18:44:00 +0100

Daily Problem

Diffstat:
A
Problems/1671.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/1671.cpp b/Problems/1671.cpp
@@ -0,0 +1,33 @@
+class Solution {
+  public:
+    int minimumMountainRemovals(const vector<int> &nums) const {
+        static int left[1001], right[1001];
+        const int n = size(nums);
+        vector<int> vec;
+        int res = 0;
+
+        for (int i = 0; i < n; i++) {
+            const auto it = lower_bound(begin(vec), end(vec), nums[i]);
+            left[i] = distance(begin(vec), it);
+            if (it != end(vec))
+                *it = nums[i];
+            else
+                vec.push_back(nums[i]);
+        }
+
+        vec.clear();
+        for (int i = n - 1; i >= 0; i--) {
+            const auto it = lower_bound(begin(vec), end(vec), nums[i]);
+            right[i] = distance(begin(vec), it);
+            if (it != end(vec))
+                *it = nums[i];
+            else
+                vec.push_back(nums[i]);
+
+            if (!left[i] || !right[i]) continue;
+            res = max(res, left[i] + right[i]);
+        }
+
+        return n - res - 1;
+    }
+};
diff --git a/README.md b/README.md
@@ -986,6 +986,7 @@ reference and a base for solving problems.
 |  1667  |    Easy    | [Fix Names in a Table](Problems/1667.cpp)                                                          |
 |  1669  |   Medium   | [Merge In Between Linked Lists](Problems/1669.cpp)                                                 |
 |  1670  |   Medium   | [Design Front Middle Back Queue](Problems/1670.cpp)                                                |
+|  1671  |    Hard    | [Minimum Number of Removals to Make Mountain Array](Problems/1671.cpp)                             |
 |  1672  |    Easy    | [Richest Customer Wealth](Problems/1672.cpp)                                                       |
 |  1673  |   Medium   | [Find the Most Competitive Subsequence](Problems/1673.cpp)                                         |
 |  1675  |    Hard    | [Minimize Deviation in Array](Problems/1675.cpp)                                                   |