Minimum operations to transform array

Array Greedy

39.4% acceptance

Feb 24, 2026

You are given two integer arrays nums1 of length n and nums2 of length n + 1. You want to transform nums1 into nums2 using the minimum number of operations. You may perform the following operations any number of times, each time choosing an index i: Increase nums1[i] by 1. Decrease nums1[i] by 1. Append nums1[i] to the end of the array. Return the minimum number of operations required to transform nums1 into nums2.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
    let n = nums1.len();
    let base: i64 = nums1.iter().zip(nums2.iter()).map(|(&a, &b)| (a - b).abs() as i64).sum();
    let last_target = nums2[n] as i64;
    // Try each i as the index to duplicate
    // Cost for position i: min_v(|nums1[i]-v| + |v-nums2[i]| + |v-last_target|) - |nums1[i]-nums2[i]|
    // = extra_cost_i
    // Total = 1 + base + min over i of extra_cost_i
    let mut min_extra = i64::MAX;
    for i in 0..n {
      let a = nums1[i] as i64;
      let b = nums2[i] as i64;
      let c = last_target;
      // min_v |a-v| + |v-b| + |v-c|: optimal v = median of (a, b, c)
      let mut vals = [a, b, c];
      vals.sort();
      let v = vals[1]; // median
      let three_cost = (a - v).abs() + (v - b).abs() + (v - c).abs();
      let two_cost = (a - b).abs(); // already in base
      let extra = three_cost - two_cost;
      min_extra = min_extra.min(extra);
    }
    1 + base + min_extra
  }
}