Skip to content

1187. Make Array Strictly Increasing

SourceWeekly Contest 153 Q4DifficultyHardRating2315

Description

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

 

Solutions

Solution 1: Dynamic Programming

Thinking

Replacements must come from \(\textit{arr2}\); we want the fewest of them. Trying every substitute at every index is too large. Let \(f[i]\) be the fewest changes so the prefix is increasing and index \(i\) is kept. Replacing the previous \(k\) positions with the \(k\) values in \(\textit{arr2}\) just below \(\textit{arr}[i]\) transitions from \(f[i-k-1]+k\). Sorted unique \(\textit{arr2}\) supports binary search; sentinels make the last index never replaced.

We define \(f[i]\) as the minimum number of operations to convert \(\textit{arr1}[0,..,i]\) into a strictly increasing array, and \(\textit{arr1}[i]\) is not replaced. Therefore, we set two sentinels \(-\infty\) and \(\infty\) at the beginning and end of \(\textit{arr1}\). The last number is definitely not replaced, so \(f[n-1]\) is the answer. We initialize \(f[0]=0\), and the rest \(f[i]=\infty\).

Next, we sort the array \(\textit{arr2}\) and remove duplicates for easy binary search.

For \(i=1,..,n-1\), we consider whether \(\textit{arr1}[i-1]\) is replaced. If \(\textit{arr1}[i-1] \lt \textit{arr1}[i]\), then \(f[i]\) can be transferred from \(f[i-1]\), that is, \(f[i] = f[i-1]\). Then, we consider the case where \(\textit{arr}[i-1]\) is replaced. Obviously, \(\textit{arr}[i-1]\) should be replaced with a number as large as possible and less than \(\textit{arr}[i]\). We perform a binary search in the array \(\textit{arr2}\) and find the first index \(j\) that is greater than or equal to \(\textit{arr}[i]\). Then we enumerate the number of replacements in the range \(k \in [1, \min(i-1, j)]\). If \(\textit{arr}[i-k-1] \lt \textit{arr2}[j-k]\), then \(f[i]\) can be transferred from \(f[i-k-1]\), that is, \(f[i] = \min(f[i], f[i-k-1] + k)\).

Finally, if \(f[n-1] \geq \infty\), it means that it cannot be converted into a strictly increasing array, return \(-1\), otherwise return \(f[n-1]\).

The time complexity is \(O(n(\log m + \min(m, n)))\), and the space complexity is \(O(n)\), where \(n\) is the length of \(\textit{arr1}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        m = 0
        for x in arr2:
            if m == 0 or x != arr2[m - 1]:
                arr2[m] = x
                m += 1
        arr2 = arr2[:m]
        arr = [-inf] + arr1 + [inf]
        n = len(arr)
        f = [inf] * n
        f[0] = 0
        for i in range(1, n):
            if arr[i - 1] < arr[i]:
                f[i] = f[i - 1]
            j = bisect_left(arr2, arr[i])
            for k in range(1, min(i - 1, j) + 1):
                if arr[i - k - 1] < arr2[j - k]:
                    f[i] = min(f[i], f[i - k - 1] + k)
        return -1 if f[n - 1] >= inf else f[n - 1]

 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
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        int m = 0;
        for (int x : arr2) {
            if (m == 0 || x != arr2[m - 1]) {
                arr2[m++] = x;
            }
        }
        final int inf = 1 << 30;
        int[] arr = new int[arr1.length + 2];
        arr[0] = -inf;
        arr[arr.length - 1] = inf;
        System.arraycopy(arr1, 0, arr, 1, arr1.length);
        int[] f = new int[arr.length];
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i - 1] < arr[i]) {
                f[i] = f[i - 1];
            }
            int j = search(arr2, arr[i], m);
            for (int k = 1; k <= Math.min(i - 1, j); ++k) {
                if (arr[i - k - 1] < arr2[j - k]) {
                    f[i] = Math.min(f[i], f[i - k - 1] + k);
                }
            }
        }
        return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1];
    }

    private int search(int[] nums, int x, int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 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
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
        const int inf = 1 << 30;
        arr1.insert(arr1.begin(), -inf);
        arr1.push_back(inf);
        int n = arr1.size();
        vector<int> f(n, inf);
        f[0] = 0;
        for (int i = 1; i < n; ++i) {
            if (arr1[i - 1] < arr1[i]) {
                f[i] = f[i - 1];
            }
            int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
            for (int k = 1; k <= min(i - 1, j); ++k) {
                if (arr1[i - k - 1] < arr2[j - k]) {
                    f[i] = min(f[i], f[i - k - 1] + k);
                }
            }
        }
        return f[n - 1] >= inf ? -1 : f[n - 1];
    }
};

 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
34
35
func makeArrayIncreasing(arr1 []int, arr2 []int) int {
    sort.Ints(arr2)
    m := 0
    for _, x := range arr2 {
        if m == 0 || x != arr2[m-1] {
            arr2[m] = x
            m++
        }
    }
    arr2 = arr2[:m]
    const inf = 1 << 30
    arr1 = append([]int{-inf}, arr1...)
    arr1 = append(arr1, inf)
    n := len(arr1)
    f := make([]int, n)
    for i := range f {
        f[i] = inf
    }
    f[0] = 0
    for i := 1; i < n; i++ {
        if arr1[i-1] < arr1[i] {
            f[i] = f[i-1]
        }
        j := sort.SearchInts(arr2, arr1[i])
        for k := 1; k <= min(i-1, j); k++ {
            if arr1[i-k-1] < arr2[j-k] {
                f[i] = min(f[i], f[i-k-1]+k)
            }
        }
    }
    if f[n-1] >= inf {
        return -1
    }
    return f[n-1]
}

 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
34
35
36
37
38
39
40
function makeArrayIncreasing(arr1: number[], arr2: number[]): number {
    arr2.sort((a, b) => a - b);
    let m = 0;
    for (const x of arr2) {
        if (m === 0 || x !== arr2[m - 1]) {
            arr2[m++] = x;
        }
    }
    arr2 = arr2.slice(0, m);
    const inf = 1 << 30;
    arr1 = [-inf, ...arr1, inf];
    const n = arr1.length;
    const f: number[] = new Array(n).fill(inf);
    f[0] = 0;
    const search = (arr: number[], x: number): number => {
        let l = 0;
        let r = arr.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (arr[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    for (let i = 1; i < n; ++i) {
        if (arr1[i - 1] < arr1[i]) {
            f[i] = f[i - 1];
        }
        const j = search(arr2, arr1[i]);
        for (let k = 1; k <= Math.min(i - 1, j); ++k) {
            if (arr1[i - k - 1] < arr2[j - k]) {
                f[i] = Math.min(f[i], f[i - k - 1] + k);
            }
        }
    }
    return f[n - 1] >= inf ? -1 : f[n - 1];
}

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        int m = 0;
        foreach (int x in arr2) {
            if (m == 0 || x != arr2[m - 1]) {
                arr2[m++] = x;
            }
        }
        int inf = 1 << 30;
        int[] arr = new int[arr1.Length + 2];
        arr[0] = -inf;
        arr[arr.Length - 1] = inf;
        for (int i = 0; i < arr1.Length; ++i) {
            arr[i + 1] = arr1[i];
        }
        int[] f = new int[arr.Length];
        Array.Fill(f, inf);
        f[0] = 0;
        for (int i = 1; i < arr.Length; ++i) {
            if (arr[i - 1] < arr[i]) {
                f[i] = f[i - 1];
            }
            int j = search(arr2, arr[i], m);
            for (int k = 1; k <= Math.Min(i - 1, j); ++k) {
                if (arr[i - k - 1] < arr2[j - k]) {
                    f[i] = Math.Min(f[i], f[i - k - 1] + k);
                }
            }
        }
        return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1];
    }

    private int search(int[] nums, int x, int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Comments