Make Array Strictly Increasing Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4
5

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

Solution

Method 1 – Dynamic Programming with Binary Search

Intuition

We use DP to track the minimum operations needed to make the array strictly increasing up to each index, considering both keeping the current value and replacing it with a value from arr2. Binary search helps efficiently find the next possible replacement.

Approach

  1. Sort arr2 and remove duplicates for efficient searching.
  2. Use a DP map: key is the previous value, value is the minimum operations to reach that state.
  3. For each index in arr1:
    • For each possible previous value in DP:
      • If arr1[i] > prev, keep arr1[i].
      • Use binary search to find the smallest value in arr2 > prev, and replace arr1[i].
    • Update DP for the next index.
  4. The answer is the minimum operations in the last DP map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        set<int> s(arr2.begin(), arr2.end());
        vector<int> b(s.begin(), s.end());
        map<int, int> dp;
        dp[-1] = 0;
        for (int a : arr1) {
            map<int, int> ndp;
            for (auto& [prev, ops] : dp) {
                if (a > prev) ndp[a] = ndp.count(a) ? min(ndp[a], ops) : ops;
                auto it = upper_bound(b.begin(), b.end(), prev);
                if (it != b.end()) ndp[*it] = ndp.count(*it) ? min(ndp[*it], ops+1) : ops+1;
            }
            dp = ndp;
        }
        if (dp.empty()) return -1;
        int ans = INT_MAX;
        for (auto& [k, v] : dp) ans = min(ans, v);
        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
34
35
36
37
38
39

func makeArrayIncreasing(arr1, arr2 []int) int {
    s := map[int]struct{}{}
    for _, x := range arr2 {
        s[x] = struct{}{}
    }
    b := []int{}
    for x := range s {
        b = append(b, x)
    }
    sort.Ints(b)
    dp := map[int]int{-1: 0}
    for _, a := range arr1 {
        ndp := map[int]int{}
        for prev, ops := range dp {
            if a > prev {
                if v, ok := ndp[a]; !ok || ops < v {
                    ndp[a] = ops
                }
            }
            idx := sort.SearchInts(b, prev+1)
            if idx < len(b) {
                if v, ok := ndp[b[idx]]; !ok || ops+1 < v {
                    ndp[b[idx]] = ops+1
                }
            }
        }
        dp = ndp
    }
    if len(dp) == 0 {
        return -1
    }
    ans := 1<<30
    for _, v := range dp {
        if v < ans {
            ans = v
        }
    }
    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

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int x : arr2) set.add(x);
        int[] b = set.stream().mapToInt(i->i).toArray();
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(-1, 0);
        for (int a : arr1) {
            Map<Integer, Integer> ndp = new HashMap<>();
            for (int prev : dp.keySet()) {
                int ops = dp.get(prev);
                if (a > prev) ndp.put(a, Math.min(ndp.getOrDefault(a, Integer.MAX_VALUE), ops));
                int idx = Arrays.binarySearch(b, prev+1);
                if (idx < 0) idx = -idx-1;
                if (idx < b.length) ndp.put(b[idx], Math.min(ndp.getOrDefault(b[idx], Integer.MAX_VALUE), ops+1));
            }
            dp = ndp;
        }
        if (dp.isEmpty()) return -1;
        int ans = Integer.MAX_VALUE;
        for (int v : dp.values()) ans = Math.min(ans, v);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun makeArrayIncreasing(arr1: IntArray, arr2: IntArray): Int {
        val set = arr2.toSet()
        val b = set.sorted()
        var dp = mutableMapOf(-1 to 0)
        for (a in arr1) {
            val ndp = mutableMapOf<Int, Int>()
            for ((prev, ops) in dp) {
                if (a > prev) ndp[a] = minOf(ndp.getOrDefault(a, Int.MAX_VALUE), ops)
                val idx = b.binarySearch(prev+1).let { if (it < 0) -it-1 else it }
                if (idx < b.size) ndp[b[idx]] = minOf(ndp.getOrDefault(b[idx], Int.MAX_VALUE), ops+1)
            }
            dp = ndp
        }
        if (dp.isEmpty()) return -1
        return dp.values.minOrNull() ?: -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def makeArrayIncreasing(self, arr1: list[int], arr2: list[int]) -> int:
        b = sorted(set(arr2))
        dp = {-1: 0}
        for a in arr1:
            ndp = {}
            for prev, ops in dp.items():
                if a > prev:
                    ndp[a] = min(ndp.get(a, float('inf')), ops)
                import bisect
                idx = bisect.bisect_right(b, prev)
                if idx < len(b):
                    ndp[b[idx]] = min(ndp.get(b[idx], float('inf')), ops+1)
            dp = ndp
        if not dp:
            return -1
        return min(dp.values())
 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

impl Solution {
    pub fn make_array_increasing(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut b = arr2.clone();
        b.sort();
        b.dedup();
        let mut dp = HashMap::new();
        dp.insert(-1, 0);
        for &a in &arr1 {
            let mut ndp = HashMap::new();
            for (&prev, &ops) in &dp {
                if a > prev {
                    ndp.insert(a, ndp.get(&a).map_or(ops, |&v| v.min(ops)));
                }
                if let Ok(idx) = b.binary_search(&(prev+1)) {
                    if idx < b.len() {
                        let v = ndp.get(&b[idx]).map_or(ops+1, |&x| x.min(ops+1));
                        ndp.insert(b[idx], v);
                    }
                } else if let Err(idx) = b.binary_search(&(prev+1)) {
                    if idx < b.len() {
                        let v = ndp.get(&b[idx]).map_or(ops+1, |&x| x.min(ops+1));
                        ndp.insert(b[idx], v);
                    }
                }
            }
            dp = ndp;
        }
        if dp.is_empty() { return -1; }
        *dp.values().min().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    makeArrayIncreasing(arr1: number[], arr2: number[]): number {
        const b = Array.from(new Set(arr2)).sort((a, b) => a - b)
        let dp = new Map<number, number>([[-1, 0]])
        for (const a of arr1) {
            const ndp = new Map<number, number>()
            for (const [prev, ops] of dp.entries()) {
                if (a > prev) ndp.set(a, Math.min(ndp.get(a) ?? Infinity, ops))
                const idx = b.findIndex(x => x > prev)
                if (idx !== -1) ndp.set(b[idx], Math.min(ndp.get(b[idx]) ?? Infinity, ops+1))
            }
            dp = ndp
        }
        if (dp.size === 0) return -1
        return Math.min(...dp.values())
    }
}

Complexity

  • ⏰ Time complexity: O(nm log m) — n is length of arr1, m is length of arr2.
  • 🧺 Space complexity: O(nm) — For DP maps.