Split and Merge Array Transformation solution and explanation

class Solution:
    def minSplitMerge(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        target = tuple(nums2)
        start = tuple(nums1)

        q = [start]
        vis = set()
        vis.add(start)

        for ans in count(0):
            t = q
            q = []
            for cur in t:
                if cur == target:
                    return ans
                for l in range(n):
                    for r in range(l, n):
                        remain = list(cur[:l]) + list(cur[r + 1 :])
                        sub = cur[l : r + 1]
                        for i in range(len(remain) + 1):
                            nxt = tuple(remain[:i] + list(sub) + remain[i:])
                            if nxt not in vis:
                                vis.add(nxt)
                                q.append(nxt)

class Solution {
    public int minSplitMerge(int[] nums1, int[] nums2) {
        int n = nums1.length;
        List<Integer> target = toList(nums2);
        List<Integer> start = toList(nums1);
        List<List<Integer>> q = List.of(start);
        Set<List<Integer>> vis = new HashSet<>();
        vis.add(start);
        for (int ans = 0;; ++ans) {
            var t = q;
            q = new ArrayList<>();
            for (var cur : t) {
                if (cur.equals(target)) {
                    return ans;
                }
                for (int l = 0; l < n; ++l) {
                    for (int r = l; r < n; ++r) {
                        List<Integer> remain = new ArrayList<>();
                        for (int i = 0; i < l; ++i) {
                            remain.add(cur.get(i));
                        }
                        for (int i = r + 1; i < n; ++i) {
                            remain.add(cur.get(i));
                        }
                        List<Integer> sub = cur.subList(l, r + 1);
                        for (int i = 0; i <= remain.size(); ++i) {
                            List<Integer> nxt = new ArrayList<>();
                            for (int j = 0; j < i; ++j) {
                                nxt.add(remain.get(j));
                            }
                            for (int x : sub) {
                                nxt.add(x);
                            }
                            for (int j = i; j < remain.size(); ++j) {
                                nxt.add(remain.get(j));
                            }
                            if (vis.add(nxt)) {
                                q.add(nxt);
                            }
                        }
                    }
                }
            }
        }
    }

    private List<Integer> toList(int[] arr) {
        List<Integer> res = new ArrayList<>(arr.length);
        for (int x : arr) {
            res.add(x);
        }
        return res;
    }
}

class Solution {
public:
    int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> target = nums2;
        vector<vector<int>> q{nums1};
        set<vector<int>> vis;
        vis.insert(nums1);

        for (int ans = 0;; ++ans) {
            vector<vector<int>> t = q;
            q.clear();
            for (auto& cur : t) {
                if (cur == target) {
                    return ans;
                }
                for (int l = 0; l < n; ++l) {
                    for (int r = l; r < n; ++r) {
                        vector<int> remain;
                        remain.insert(remain.end(), cur.begin(), cur.begin() + l);
                        remain.insert(remain.end(), cur.begin() + r + 1, cur.end());
                        vector<int> sub(cur.begin() + l, cur.begin() + r + 1);
                        for (int i = 0; i <= (int) remain.size(); ++i) {
                            vector<int> nxt;
                            nxt.insert(nxt.end(), remain.begin(), remain.begin() + i);
                            nxt.insert(nxt.end(), sub.begin(), sub.end());
                            nxt.insert(nxt.end(), remain.begin() + i, remain.end());

                            if (!vis.count(nxt)) {
                                vis.insert(nxt);
                                q.push_back(nxt);
                            }
                        }
                    }
                }
            }
        }
    }
};

func minSplitMerge(nums1 []int, nums2 []int) int {
	n := len(nums1)

	toArr := func(nums []int) [6]int {
		var t [6]int
		for i, x := range nums {
			t[i] = x
		}
		return t
	}

	start := toArr(nums1)
	target := toArr(nums2)

	vis := map[[6]int]bool{start: true}
	q := [][6]int{start}

	for ans := 0; ; ans++ {
		nq := [][6]int{}
		for _, cur := range q {
			if cur == target {
				return ans
			}
			for l := 0; l < n; l++ {
				for r := l; r < n; r++ {
					remain := []int{}
					for i := 0; i < l; i++ {
						remain = append(remain, cur[i])
					}
					for i := r + 1; i < n; i++ {
						remain = append(remain, cur[i])
					}

					sub := []int{}
					for i := l; i <= r; i++ {
						sub = append(sub, cur[i])
					}

					for pos := 0; pos <= len(remain); pos++ {
						nxtSlice := []int{}
						nxtSlice = append(nxtSlice, remain[:pos]...)
						nxtSlice = append(nxtSlice, sub...)
						nxtSlice = append(nxtSlice, remain[pos:]...)

						nxt := toArr(nxtSlice)
						if !vis[nxt] {
							vis[nxt] = true
							nq = append(nq, nxt)
						}
					}
				}
			}
		}
		q = nq
	}
}