leetcode

commit 65b51cdaee72b4f153aba29b03b437bfa573cbc4
parent de1096dc2000befc3a2c37e4bc483d2db50c3dcc
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 17 Jun 2023 17:49:56 +0200

Daily Problem

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

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/1187.cpp b/Problems/1187.cpp
@@ -0,0 +1,33 @@
+class Solution {
+  int dp[2001][2001][2];
+
+  void norm(vector<int> &arr) {
+    sort(arr.begin(), arr.end());
+    int i = 1, j = 1;
+    while (i < arr.size()) {
+      if (arr[i] != arr[i - 1]) arr[j++] = arr[i];
+      i++;
+    }
+    arr.resize(j);
+  }
+
+  int rec(const vector<int> &arr1, const vector<int> &arr2, int i, int j,
+          bool other) {
+    if (i >= arr1.size()) return 0;
+    int prev = !other ? i == 0 ? INT_MIN : arr1[i - 1] : arr2[j];
+    j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
+    if (dp[i][j][other]) return dp[i][j][other];
+
+    int res = 2002;
+    if (j < arr2.size()) res = rec(arr1, arr2, i + 1, j, true) + 1;
+    if (prev < arr1[i]) res = min(res, rec(arr1, arr2, i + 1, j, false));
+    return dp[i][j][other] = res;
+  }
+
+public:
+  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
+    norm(arr2);
+    int res = rec(arr1, arr2, 0, 0, false);
+    return res >= 2002 ? -1 : res;
+  }
+};
diff --git a/README.md b/README.md
@@ -425,6 +425,7 @@ for solving problems.
 |  1146  |   Medium   | [Snapshot Array](Problems/1146.cpp)                                                              |
 |  1161  |   Medium   | [Maximum Level Sum of a Binary Tree](Problems/1161.cpp)                                                             |
 |  1162  |   Medium   | [As Far from Land as Possible](Problems/1162.cpp)                                                |
+|  1187  |    Hard    | [Make Array Strictly Increasing](Problems/1187.cpp)                                              |
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |
 |  1209  |   Medium   | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)                                 |
 |  1232  |    Easy    | [Check If It Is a Straight Line](Problems/1232.cpp)                                              |