Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 17

Description

Make Array Strictly Increasing

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  int solve(
    int pos,
    int left,
    const vector<int> &arr1,
    const vector<int> &arr2,
    vector<map<int, int>> &dp
  ) {
    if(pos == arr1.size()) return 0;

    if(dp[pos].count(left)) return dp[pos][left];

    int exclude = INT_MAX;
    int include = INT_MAX;

    if(arr1[pos] > left) {
      exclude = solve(pos + 1, arr1[pos], arr1, arr2, dp);
    }
    int replace = upper_bound(arr2.begin(), arr2.end(), left) - arr2.begin();
    if(replace != arr2.size()) {
      include = solve(pos + 1, arr2[replace], arr1, arr2, dp);
    }
    if(include == INT_MAX) {
      dp[pos][left] = exclude;
    } else {
      dp[pos][left] = min(exclude, include + 1);
    }
    return dp[pos][left];
  }
public:
  int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    sort(arr2.begin(), arr2.end());
    vector<map<int, int>> dp(2001);

    int result = solve(0, INT_MIN, arr1, arr2, dp);
    if(result == INT_MAX) return -1;
    return result;
  }
};

// Accepted
// 21/21 cases passed (897 ms)
// Your runtime beats 12.21 % of cpp submissions
// Your memory usage beats 11.05 % of cpp submissions (80.1 MB)

2023-06-17 Daily Challenge

June LeetCoding Challenge 17

Description

Solution