leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1187.cpp (1033B)

      1 class Solution {
      2     int dp[2001][2001][2];
      3 
      4     void norm(vector<int> &arr) {
      5         sort(arr.begin(), arr.end());
      6         int i = 1, j = 1;
      7         while (i < arr.size()) {
      8             if (arr[i] != arr[i - 1]) arr[j++] = arr[i];
      9             i++;
     10         }
     11         arr.resize(j);
     12     }
     13 
     14     int rec(const vector<int> &arr1, const vector<int> &arr2, int i, int j, bool other) {
     15         if (i >= arr1.size()) return 0;
     16         int prev = !other ? i == 0 ? INT_MIN : arr1[i - 1] : arr2[j];
     17         j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
     18         if (dp[i][j][other]) return dp[i][j][other];
     19 
     20         int res = 2002;
     21         if (j < arr2.size()) res = rec(arr1, arr2, i + 1, j, true) + 1;
     22         if (prev < arr1[i]) res = min(res, rec(arr1, arr2, i + 1, j, false));
     23         return dp[i][j][other] = res;
     24     }
     25 
     26   public:
     27     int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
     28         norm(arr2);
     29         int res = rec(arr1, arr2, 0, 0, false);
     30         return res >= 2002 ? -1 : res;
     31     }
     32 };