Constructing two increasing arrays

Array Dynamic Programming

62.7% acceptance

Mar 31, 2026

Given 2 integer arrays nums1 and nums2 consisting only of 0 and 1, your task is to calculate the minimum possible largest number in arrays nums1 and nums2, after doing the following. Replace every 0 with an even positive integer and every 1 with an odd positive integer. After replacement, both arrays should be increasing and each integer should be used at most once. Return the minimum possible largest number after applying the changes.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_largest(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let n1 = nums1.len();
    let n2 = nums2.len();
    let mut dp = vec![vec![i32::MAX; n2 + 1]; n1 + 1];
    dp[0][0] = 0;

    for i in 0..=n1 {
      for j in 0..=n2 {
        if dp[i][j] == i32::MAX {
          continue;
        }
        let last = dp[i][j];
        if i < n1 {
          let p = nums1[i];
          let nv = if last % 2 == p { last + 2 } else { last + 1 };
          dp[i + 1][j] = dp[i + 1][j].min(nv);
        }
        if j < n2 {
          let p = nums2[j];
          let nv = if last % 2 == p { last + 2 } else { last + 1 };
          dp[i][j + 1] = dp[i][j + 1].min(nv);
        }
      }
    }

    dp[n1][n2]
  }
}