Make array strictly increasing

Array Binary Search Dynamic Programming Sorting

57.9% acceptance

Feb 25, 2026

2343

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_array_increasing(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
    // dp: HashMap from last value -> min operations
    // For each position, we can keep arr1[i] or replace with some value from arr2
    use std::collections::HashMap;
    let mut arr2_sorted: Vec<i32> = arr2.clone();
    arr2_sorted.sort();
    arr2_sorted.dedup();
    // dp maps (last_value) -> min_ops
    let mut dp: HashMap<i32, i32> = HashMap::new();
    dp.insert(i32::MIN, 0);
    for &v in &arr1 {
      let mut new_dp: HashMap<i32, i32> = HashMap::new();
      for (&last, &ops) in &dp {
        // Option 1: keep arr1[i] if v > last
        if v > last {
          let e = new_dp.entry(v).or_insert(i32::MAX);
          *e = (*e).min(ops);
        }
        // Option 2: replace arr1[i] with smallest value in arr2 > last
        let idx = arr2_sorted.partition_point(|&x| x <= last);
        if idx < arr2_sorted.len() {
          let replacement = arr2_sorted[idx];
          let e = new_dp.entry(replacement).or_insert(i32::MAX);
          *e = (*e).min(ops + 1);
        }
      }
      dp = new_dp;
    }
    if dp.is_empty() {
      -1
    } else {
      *dp.values().min().unwrap()
    }
  }
}