Split and merge array transformation

Array Hash Table Breadth-First Search

58.6% acceptance

Feb 25, 2026

You are given two integer arrays nums1 and nums2, each of length n. You may perform the following split-and-merge operation on nums1 any number of times: Choose a subarray nums1[L..R]. Remove that subarray, leaving the prefix nums1[0..L-1] (empty if L = 0) and the suffix nums1[R+1..n-1] (empty if R = n - 1). Re-insert the removed subarray (in its original order) at any position in the remaining array (i.e., between any two elements, at the very start, or at the very end). Return the minimum number of split-and-merge operations needed to transform nums1 into nums2.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_split_merge(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    // n <= 6, so BFS over all permutations of the array.
    use std::collections::{HashMap, VecDeque};
    let target = nums2.clone();
    if nums1 == target { return 0; }
    let mut visited: HashMap<Vec<i32>, i32> = HashMap::new();
    let mut queue: VecDeque<(Vec<i32>, i32)> = VecDeque::new();
    queue.push_back((nums1, 0));
    while let Some((cur, steps)) = queue.pop_front() {
      if visited.contains_key(&cur) { continue; }
      visited.insert(cur.clone(), steps);
      if cur == target { return steps; }
      let n = cur.len();
      for l in 0..n {
        for r in l..n {
          // Extract subarray cur[l..=r]
          let sub: Vec<i32> = cur[l..=r].to_vec();
          let rest: Vec<i32> = [&cur[..l], &cur[r+1..]].concat();
          // Insert sub at any valid position in rest
          for pos in 0..=rest.len() {
            let mut next = rest.clone();
            next.splice(pos..pos, sub.iter().cloned());
            if !visited.contains_key(&next) {
              if next == target { return steps + 1; }
              queue.push_back((next, steps + 1));
            }
          }
        }
      }
    }
    -1
  }
}