Skip to content

1187. Make Array Strictly Increasing 👍

  • Time: $O(|\texttt{arr1}| \log |\texttt{arr2}|)$
  • Space: $O(|\texttt{arr1}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    // dp[i] := min steps to reach i at previous round
    unordered_map<int, int> dp{{-1, 0}};

    sort(begin(arr2), end(arr2));

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

    int ans = INT_MAX;
    for (const auto& [_, steps] : dp)
      ans = min(ans, steps);
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int makeArrayIncreasing(int[] arr1, int[] arr2) {
    // dp[i] := min 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> nextDp = new HashMap<>();
      for (final int val : dp.keySet()) {
        final int steps = dp.get(val);
        // it's possible to use the value in arr1
        if (a > val)
          nextDp.put(a, Math.min(nextDp.getOrDefault(a, Integer.MAX_VALUE), steps));
        // also try the value in arr2
        final int i = firstGreater(arr2, val);
        if (i < arr2.length)
          nextDp.put(arr2[i], Math.min(nextDp.getOrDefault(arr2[i], Integer.MAX_VALUE), steps + 1));
      }
      if (nextDp.isEmpty())
        return -1;
      dp = nextDp;
    }

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

  private int firstGreater(int[] A, int val) {
    final int i = Arrays.binarySearch(A, val + 1);
    return i < 0 ? -(i + 1) : i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
    # dp[i] := min steps to reach i at previous round
    dp = {-1: 0}

    arr2.sort()

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

    return min(dp.values())