1187. Make Array Strictly Increasing LeetCode Solution

In this guide, you will get 1187. Make Array Strictly Increasing LeetCode Solution with the best time and space complexity. The solution to Make Array Strictly Increasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Make Array Strictly Increasing solution in C++
Make Array Strictly Increasing solution in Java
Make Array Strictly Increasing solution in Python
Additional Resources

1187. Make Array Strictly Increasing LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(|\texttt{arr1}|)

1187. Make Array Strictly Increasing LeetCode Solution in C++

class Solution {
 public:
  int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    // dp[i] := the minimum steps to reach i at previous round
    unordered_map<int, int> dp{{-1, 0}};

    ranges::sort(arr2);

    for (const int a : arr1) {
      unordered_map<int, int> newDp;
      for (const auto& [val, steps] : dp) {
        // It's possible to use the value in the arr1.
        if (a > val)
          newDp[a] = min(newDp.contains(a) ? newDp[a] : INT_MAX, steps);
        // Also try the value in the arr2.
        if (const auto it = ranges::upper_bound(arr2, val); it != arr2.cend())
          newDp[*it] =
              min(newDp.contains(*it) ? newDp[*it] : INT_MAX, steps + 1);
      }
      if (newDp.empty())
        return -1;
      dp = std::move(newDp);
    }

    int ans = INT_MAX;
    for (const auto& [_, steps] : dp)
      ans = min(ans, steps);
    return ans;
  }
};
/* code provided by PROGIEZ */

1187. Make Array Strictly Increasing LeetCode Solution in Java

class Solution {
  public int makeArrayIncreasing(int[] arr1, int[] arr2) {
    // dp[i] := the minimum steps to reach i at previous round
    Map<Integer, Integer> dp = new HashMap<>();
    dp.put(-1, 0);

    Arrays.sort(arr2);

    for (final int a : arr1) {
      Map<Integer, Integer> newDp = new HashMap<>();
      for (final int val : dp.keySet()) {
        final int steps = dp.get(val);
        // It's possible to use the value in the arr1.
        if (a > val)
          newDp.put(a, Math.min(newDp.getOrDefault(a, Integer.MAX_VALUE), steps));
        // Also try the value in the arr2.
        final int i = firstGreater(arr2, val);
        if (i < arr2.length)
          newDp.put(arr2[i], Math.min(newDp.getOrDefault(arr2[i], Integer.MAX_VALUE), steps + 1));
      }
      if (newDp.isEmpty())
        return -1;
      dp = newDp;
    }

    return Collections.min(dp.values());
  }

  private int firstGreater(int[] arr, int target) {
    final int i = Arrays.binarySearch(arr, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

1187. Make Array Strictly Increasing LeetCode Solution in Python

class Solution:
  def makeArrayIncreasing(self, arr1: list[int], arr2: list[int]) -> int:
    # dp[i] := the minimum steps to reach i at previous round
    dp = {-1: 0}

    arr2.sort()

    for a in arr1:
      newDp = collections.defaultdict(lambda: math.inf)
      for val, steps in dp.items():
        # It's possible to use the value in the arr1.
        if a > val:
          newDp[a] = min(newDp[a], steps)
        # Also try the value in the arr2.
        i = bisect_right(arr2, val)
        if i < len(arr2):
          newDp[arr2[i]] = min(newDp[arr2[i]], steps + 1)
      if not newDp:
        return -1
      dp = newDp

    return min(dp.values())
 # code by PROGIEZ