Minimum swaps to make sequences increasing

Array Dynamic Programming

41.3% acceptance

Feb 22, 2026

2941

138

You are given two integer arrays of the same length nums1 and nums2. In one operation, you are allowed to swap nums1[i] with nums2[i]. For example, if nums1 = [1,2,3,8], and nums2 = [5,6,7,4], you can swap the element at i = 3 to obtain nums1 = [1,2,3,4] and nums2 = [5,6,7,8]. Return the minimum number of needed operations to make nums1 and nums2 strictly increasing. The test cases are generated so that the given input always makes it possible. An array arr is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1].

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let n = nums1.len();
    let mut keep = 0i32; // min swaps if no swap at i
    let mut swap = 1i32; // min swaps if swap at i
    for i in 1..n {
      let (mut nk, mut ns) = (i32::MAX, i32::MAX);
      // no swap or both swap when natural order holds
      if nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] {
        nk = nk.min(keep);
        ns = ns.min(swap + 1);
      }
      // cross: prev swapped and curr not, or vice versa
      if nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] {
        nk = nk.min(swap);
        ns = ns.min(keep + 1);
      }
      keep = nk;
      swap = ns;
    }
    keep.min(swap)

  }
}