Skip to content

3690. Split and Merge Array Transformation

Description

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:

  1. Choose a subarray nums1[L..R].
  2. 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).
  3. 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.

 

Example 1:

Input: nums1 = [3,1,2], nums2 = [1,2,3]

Output: 1

Explanation:

  • Split out the subarray [3] (L = 0, R = 0); the remaining array is [1,2].
  • Insert [3] at the end; the array becomes [1,2,3].

Example 2:

Input: nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]

Output: 3

Explanation:

  • Remove [1,1,2] at indices 0 - 2; remaining is [3,4,5]; insert [1,1,2] at position 2, resulting in [3,4,1,1,2,5].
  • Remove [4,1,1] at indices 1 - 3; remaining is [3,2,5]; insert [4,1,1] at position 3, resulting in [3,2,5,4,1,1].
  • Remove [3,2] at indices 0 - 1; remaining is [5,4,1,1]; insert [3,2] at position 2, resulting in [5,4,3,2,1,1].

 

Constraints:

  • 2 <= n == nums1.length == nums2.length <= 6
  • -105 <= nums1[i], nums2[i] <= 105
  • nums2 is a permutation of nums1.

Solutions

Solution 1: BFS

We can use Breadth-First Search (BFS) to solve this problem. Since the array length is at most 6, we can enumerate all possible split and merge operations to find the minimum number of operations.

First, we define a queue \(\textit{q}\) to store the current array states, and use a set \(\textit{vis}\) to record the visited array states to avoid duplicate computations. Initially, the queue contains only the array \(\textit{nums1}\).

Then, we perform the following steps:

  1. Remove the current array state \(\textit{cur}\) from the queue.
  2. If \(\textit{cur}\) equals the target array \(\textit{nums2}\), return the current number of operations.
  3. Otherwise, enumerate all possible split positions \((l, r)\), remove the subarray \(\textit{cur}[l..r]\) to obtain the remaining array \(\textit{remain}\) and the subarray \(\textit{sub}\).
  4. Insert the subarray \(\textit{sub}\) into all possible positions of the remaining array \(\textit{remain}\) to generate new array states \(\textit{nxt}\).
  5. If a new array state \(\textit{nxt}\) has not been visited, add it to the queue and the visited set.
  6. Repeat the above steps until the target array is found or the queue is empty.

The time complexity is \(O(n! \times n^4)\), and the space complexity is \(O(n! \times n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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);
                            }
                        }
                    }
                }
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
    }
}

Comments