Make Array Strictly Increasing LeetCode solution in C++

1
// recursive (TLE)
2
class Solution {
3
 public:
4
  int getMin(vector<int> &arr1, vector<int> &arr2, int i, int j, int prev, bool flag) {
5
    if (i == arr1.size()) return 0;
6

7
    while (j < arr2.size() && arr2[j] <= prev) j++;
8

9
    if (arr1[i] <= prev && j == arr2.size()) return 2001;
10

11
    int take = 2001;
12
    int ignore = 2001;
13
    if (j != arr2.size()) take = 1 + getMin(arr1, arr2, i + 1, j + 1, arr2[j], false);
14
    if (arr1[i] > prev) ignore = getMin(arr1, arr2, i + 1, j, arr1[i], true);
15

16
    return min(take, ignore);
17
  }
18
  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
19
    sort(arr2.begin(), arr2.end());
20

21
    int temp = getMin(arr1, arr2, 0, 0, -1, true);
22
    if (temp > arr1.size()) return -1;
23

24
    return temp;
25
  }
26
};
27

28
// memoization (accepted but took 1543 ms )
29
class Solution {
30
  int dp[2001][2001][2];
31

32
 public:
33
  int getMin(vector<int> &arr1, vector<int> &arr2, int i, int j, int prev, bool flag) {
34
    if (i == arr1.size()) return 0;
35
    if (dp[i][j][flag] != -1) return dp[i][j][flag];
36

37
    while (j < arr2.size() && arr2[j] <= prev) j++;
38

39
    if (arr1[i] <= prev && j == arr2.size()) return 2001;
40

41
    int take = 2001;
42
    int ignore = 2001;
43
    if (j != arr2.size()) take = 1 + getMin(arr1, arr2, i + 1, j + 1, arr2[j], false);
44
    if (arr1[i] > prev) ignore = getMin(arr1, arr2, i + 1, j, arr1[i], true);
45

46
    return dp[i][j][flag] = min(take, ignore);
47
  }
48
  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
49
    sort(arr2.begin(), arr2.end());
50
    memset(dp, -1, sizeof dp);
51

52
    int temp = getMin(arr1, arr2, 0, 0, -1, true);
53
    if (temp > arr1.size()) return -1;
54

55
    return temp;
56
  }
57
};
58

59
// Binary Search in finding next j
60
class Solution {
61
  int dp[2001][2001];
62
  int getNext(vector<int> &arr2, int prev, int start) {
63
    int ans = arr2.size();
64
    int l = start;
65
    int h = ans - 1;
66
    while (l <= h) {
67
      int mid = (l + h) / 2;
68
      if (arr2[mid] > prev) {
69
        ans = mid;
70
        h = mid - 1;
71
      } else {
72
        l = mid + 1;
73
      }
74
    }
75
    return ans;
76
  }
77

78
 public:
79
  int getMin(vector<int> &arr1, vector<int> &arr2, int i, int k, int prev) {
80
    if (i == arr1.size()) return 0;
81
    int j = getNext(arr2, prev, k);
82
    if (dp[i][j] != -1) return dp[i][j];
83
    if (arr1[i] <= prev && j == arr2.size()) return 2001;
84

85
    int take = 2001;
86
    int ignore = 2001;
87
    if (j != arr2.size()) take = 1 + getMin(arr1, arr2, i + 1, j + 1, arr2[j]);
88
    if (arr1[i] > prev) ignore = getMin(arr1, arr2, i + 1, j, arr1[i]);
89

90
    return dp[i][j] = min(take, ignore);
91
  }
92
  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
93
    sort(arr2.begin(), arr2.end());
94
    memset(dp, -1, sizeof dp);
95

96
    int temp = getMin(arr1, arr2, 0, 0, -1);
97
    if (temp > arr1.size()) return -1;
98

99
    return temp;
100
  }
101
};