3690. Split and Merge Array Transformation

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integer arrays nums1 and nums2, both of the same length n. Your goal is to transform nums1 into nums2 using as few split-and-merge operations as possible.

A single split-and-merge operation works like this:

Pick a contiguous subarray nums1[L..R] from the current array.
Remove it, which leaves behind the prefix nums1[0..L-1] (possibly empty if L = 0) and the suffix nums1[R+1..n-1] (possibly empty if R = n - 1), joined together as one shorter array.
Re-insert the removed subarray — keeping its elements in their original order — at any position in the remaining array: at the very beginning, at the very end, or between any two elements.

In other words, each operation lets you cut out one contiguous block of elements and paste it somewhere else in the array, without changing the internal order of that block.

Return the minimum number of such operations required to make nums1 exactly equal to nums2.

For example, if nums1 = [3, 1, 2] and nums2 = [1, 2, 3], you can cut out the subarray [3] and insert it at the end, producing [1, 2, 3] in just 1 operation.

Key points to note:

The two arrays are guaranteed to have the same length, and the array length is small (at most 6), so the total number of distinct arrangements is limited.
Every operation moves exactly one contiguous block; you cannot reverse or reorder the elements within the block.
Since each operation can change the array significantly, the answer is often very small, which makes an exhaustive search over array states feasible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why BFS?

This problem maps to BFS through a short path in the full flowchart.

Modeling array states as graph nodes with operations as edges turns the problem into a shortest-path search, which BFS solves optimally on an unweighted graph.

Open in Flowchart

Intuition

The first thing to notice is the constraint: the array length is at most 6. This is a strong hint that brute force is intended, because the number of distinct orderings of the array is tiny — at most 6! = 720 permutations (and even fewer when there are duplicate values).

Now think of each possible arrangement of the array as a state, and each split-and-merge operation as an edge connecting one state to another. The question "what is the minimum number of operations to turn nums1 into nums2?" becomes a classic question: what is the shortest path from the starting state to the target state in this state graph?

Whenever we need the shortest path in an unweighted graph (every operation costs exactly 1), Breadth-First Search (BFS) is the natural tool. BFS explores all states reachable in 0 operations, then 1 operation, then 2, and so on — so the first time we encounter the target array, we are guaranteed to have found it with the minimum number of operations.

Why is this efficient enough?

From any state, the number of possible moves is bounded: there are O(n^2) choices for the subarray [l, r] and O(n) insertion positions, giving roughly O(n^3) neighbors per state — at most a few hundred when n = 6.
The total number of states is at most 720, so even visiting every state with all its transitions is trivial work.

One more detail makes this work: we must track visited states with a set. Different sequences of operations can produce the same array, and without deduplication the search would revisit the same arrangements endlessly. Storing each array as an immutable tuple lets us put it in a hash set and skip anything we've already seen.

So the path to the solution is: tiny input size → model arrangements as graph nodes and operations as edges → shortest path in an unweighted graph → BFS with a visited set.

Solution Approach

The solution implements a level-by-level BFS over array states, where each state is a tuple representing one arrangement of the array.

Data Structures

Tuples for states: Lists are not hashable in Python, so each array arrangement is converted to a tuple (start = tuple(nums1), target = tuple(nums2)). Tuples can be stored in a set and compared directly.
q (a list): Holds all states at the current BFS level (i.e., all arrangements reachable in exactly ans operations).
vis (a set): Records every state ever generated, so no arrangement is processed twice.

Step-by-Step Walkthrough

1. Initialization

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

The search begins with only the original array nums1, marked as visited.

2. Level-by-level expansion

for ans in count(0):
    t = q
    q = []

Instead of a traditional queue with a stored depth per node, the code processes the BFS one full level at a time. The variable ans from count(0) (an infinite counter 0, 1, 2, ...) is exactly the number of operations performed so far. At each iteration, t holds the current level's states and q is reset to collect the next level.

3. Check for the target

for cur in t:
    if cur == target:
        return ans

If any state in the current level equals nums2, we return ans immediately. Because BFS explores states in order of increasing operation count, this is guaranteed to be the minimum.

4. Generate all neighbors of a state

For each state cur, we simulate every possible split-and-merge operation:

for l in range(n):
    for r in range(l, n):
        remain = list(cur[:l]) + list(cur[r + 1:])
        sub = cur[l:r + 1]

The pair (l, r) enumerates every contiguous subarray to cut out.
remain is what's left after removing cur[l..r].
sub is the removed block, kept in its original order.

Then the block is re-inserted at every possible position:

for i in range(len(remain) + 1):
    nxt = tuple(remain[:i] + list(sub) + remain[i:])

i = 0 inserts at the very front, i = len(remain) at the very end, and everything in between covers all middle positions.
The result is converted back to a tuple so it can be hashed.

5. Deduplicate and enqueue

if nxt not in vis:
    vis.add(nxt)
    q.append(nxt)

Only never-before-seen arrangements are added to the next level. Marking states as visited at insertion time (rather than when dequeued) prevents the same state from being added to q multiple times within one level.

6. Repeat

The outer for ans in count(0) loop advances to the next level, incrementing the operation count by 1, until the target is found. Since nums2 is a permutation of nums1 and every arrangement is reachable, termination is guaranteed.

Complexity Analysis

Let n be the array length (at most 6):

States: at most n! distinct arrangements (720 for n = 6).
Transitions per state: O(n^2) subarray choices × O(n) insertion positions = O(n^3), and building each new tuple costs O(n).
Time complexity: O(n! × n^4) in the worst case — comfortably small for n ≤ 6.
Space complexity: O(n! × n) for the visited set and queue, since each stored state takes O(n) space.

Example Walkthrough

Let's trace the BFS on a small but non-trivial case:

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

Setup

start  = (3, 2, 1)
target = (1, 2, 3)
q   = [(3, 2, 1)]
vis = {(3, 2, 1)}

Level 0 (ans = 0)

The only state in q is (3, 2, 1), which is not the target, so we expand it. We enumerate every cut (l, r) and every insertion position i:

Cut `(l, r)`	Removed block `sub`	`remain`	New states produced
`(0, 0)`	`[3]`	`[2, 1]`	`(3,2,1)`✗dup, `(2,3,1)`✓, `(2,1,3)`✓
`(0, 1)`	`[3, 2]`	`[1]`	`(3,2,1)`✗dup, `(1,3,2)`✓
`(0, 2)`	`[3, 2, 1]`	`[]`	`(3,2,1)`✗dup
`(1, 1)`	`[2]`	`[3, 1]`	`(2,3,1)`✗dup, `(3,2,1)`✗dup, `(3,1,2)`✓
`(1, 2)`	`[2, 1]`	`[3]`	`(2,1,3)`✗dup, `(3,2,1)`✗dup
`(2, 2)`	`[1]`	`[3, 2]`	`(1,3,2)`✗dup, `(3,1,2)`✗dup, `(3,2,1)`✗dup

Notice how the visited set does its job: many different cut/insert combinations regenerate arrangements we've already seen, and they are all skipped at insertion time.

After level 0, the next level is:

q   = [(2, 3, 1), (2, 1, 3), (1, 3, 2), (3, 1, 2)]
vis = {(3,2,1), (2,3,1), (2,1,3), (1,3,2), (3,1,2)}

A key observation here: (1, 2, 3) did not appear, which proves the answer is strictly greater than 1. No single split-and-merge can sort [3, 2, 1], because every one-block move leaves 3 before 2, or 2 before 1, somewhere in the array.

Level 1 (ans = 1)

We scan the four states — none equals (1, 2, 3) — and expand each one. Take (2, 3, 1) as an example:

Cut (l, r) = (2, 2): sub = [1], remain = [2, 3].
Insert at position i = 0: nxt = (1, 2, 3) — a brand-new state, added to q and vis.

Other states reach the target too, showing multiple shortest paths exist:

From (2, 1, 3): cut [2], insert it between 1 and 3 → (1, 2, 3).
From (1, 3, 2): cut [3], insert it at the end → (1, 2, 3).
From (3, 1, 2): cut [3], insert it at the end → (1, 2, 3).

Since vis already contains (1, 2, 3) after the first discovery, the duplicates are filtered out and the state is enqueued exactly once.

Level 2 (ans = 2)

The new level begins, ans advances to 2, and the very first check finds:

cur == target == (1, 2, 3)  →  return 2

Answer: 2 — for instance, [3, 2, 1] → [2, 3, 1] (move [3] after 2), then [2, 3, 1] → [1, 2, 3] (move [1] to the front).

The walkthrough highlights why BFS is the right tool: all 6 permutations of a length-3 array were organized into layers by operation count (1 state at distance 0, 4 at distance 1, 1 at distance 2), and the first time the target surfaced, its layer number was guaranteed to be the minimum number of operations.

Solution Implementation

1from itertools import count
2from typing import List
3
4
5class Solution:
6    def minSplitMerge(self, nums1: List[int], nums2: List[int]) -> int:
7        n = len(nums1)
8        target = tuple(nums2)  # the goal state we want to reach
9        start = tuple(nums1)   # the initial state
10
11        # BFS queue holding all states at the current level (i.e., reachable
12        # with exactly `step` operations), plus a visited set to avoid
13        # re-processing the same state.
14        queue = [start]
15        visited = {start}
16
17        # `step` counts the number of split-and-merge operations performed.
18        for step in count(0):
19            current_level = queue
20            queue = []
21
22            for state in current_level:
23                # If the current state matches the target, `step` operations
24                # were enough — return it.
25                if state == target:
26                    return step
27
28                # Enumerate every contiguous subarray [left, right] to remove.
29                for left in range(n):
30                    for right in range(left, n):
31                        # Elements remaining after removing the subarray.
32                        remaining = list(state[:left]) + list(state[right + 1:])
33                        # The removed subarray to be re-inserted.
34                        subarray = list(state[left:right + 1])
35
36                        # Try inserting the subarray at every possible position.
37                        for pos in range(len(remaining) + 1):
38                            next_state = tuple(
39                                remaining[:pos] + subarray + remaining[pos:]
40                            )
41                            if next_state not in visited:
42                                visited.add(next_state)
43                                queue.append(next_state)
44

1class Solution {
2    public int minSplitMerge(int[] nums1, int[] nums2) {
3        int n = nums1.length;
4
5        // Convert both arrays to lists for easier state comparison and hashing
6        List<Integer> target = toList(nums2);
7        List<Integer> start = toList(nums1);
8
9        // BFS queue: each element is one reachable arrangement of nums1
10        List<List<Integer>> queue = List.of(start);
11
12        // Visited set to avoid revisiting the same arrangement
13        Set<List<Integer>> visited = new HashSet<>();
14        visited.add(start);
15
16        // BFS level by level; 'steps' is the number of operations performed
17        for (int steps = 0;; ++steps) {
18            List<List<Integer>> currentLevel = queue;
19            queue = new ArrayList<>();
20
21            for (List<Integer> current : currentLevel) {
22                // If the current arrangement matches the target, return the step count
23                if (current.equals(target)) {
24                    return steps;
25                }
26
27                // Enumerate every subarray [left, right] to remove
28                for (int left = 0; left < n; ++left) {
29                    for (int right = left; right < n; ++right) {
30                        // Build the remaining list after removing the subarray
31                        List<Integer> remaining = new ArrayList<>();
32                        for (int i = 0; i < left; ++i) {
33                            remaining.add(current.get(i));
34                        }
35                        for (int i = right + 1; i < n; ++i) {
36                            remaining.add(current.get(i));
37                        }
38
39                        // The removed subarray to be reinserted
40                        List<Integer> subarray = current.subList(left, right + 1);
41
42                        // Try inserting the subarray at every possible position
43                        for (int pos = 0; pos <= remaining.size(); ++pos) {
44                            List<Integer> next = new ArrayList<>();
45                            // Elements before the insertion point
46                            for (int j = 0; j < pos; ++j) {
47                                next.add(remaining.get(j));
48                            }
49                            // The reinserted subarray
50                            for (int x : subarray) {
51                                next.add(x);
52                            }
53                            // Elements after the insertion point
54                            for (int j = pos; j < remaining.size(); ++j) {
55                                next.add(remaining.get(j));
56                            }
57
58                            // Enqueue the new arrangement if it has not been visited
59                            if (visited.add(next)) {
60                                queue.add(next);
61                            }
62                        }
63                    }
64                }
65            }
66        }
67    }
68
69    // Helper method: convert an int array into a List<Integer>
70    private List<Integer> toList(int[] arr) {
71        List<Integer> result = new ArrayList<>(arr.length);
72        for (int x : arr) {
73            result.add(x);
74        }
75        return result;
76    }
77}
78

1class Solution {
2public:
3    int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
4        int n = nums1.size();
5
6        // The target state we want to reach.
7        vector<int> target = nums2;
8
9        // BFS queue (processed level by level), starting from the initial array.
10        vector<vector<int>> queue{nums1};
11
12        // Visited set to avoid revisiting the same array state.
13        set<vector<int>> visited;
14        visited.insert(nums1);
15
16        // BFS: 'steps' counts how many split-merge operations have been applied.
17        for (int steps = 0;; ++steps) {
18            // Take a snapshot of the current level and clear the queue
19            // so it can collect states of the next level.
20            vector<vector<int>> currentLevel = queue;
21            queue.clear();
22
23            for (auto& current : currentLevel) {
24                // If the current state matches the target, return the step count.
25                if (current == target) {
26                    return steps;
27                }
28
29                // Enumerate every subarray [left, right] to remove.
30                for (int left = 0; left < n; ++left) {
31                    for (int right = left; right < n; ++right) {
32                        // 'remaining' is the array with the subarray removed.
33                        vector<int> remaining;
34                        remaining.insert(remaining.end(), current.begin(), current.begin() + left);
35                        remaining.insert(remaining.end(), current.begin() + right + 1, current.end());
36
37                        // 'segment' is the removed subarray.
38                        vector<int> segment(current.begin() + left, current.begin() + right + 1);
39
40                        // Try re-inserting the segment at every possible position.
41                        for (int pos = 0; pos <= (int) remaining.size(); ++pos) {
42                            vector<int> next;
43                            next.insert(next.end(), remaining.begin(), remaining.begin() + pos);
44                            next.insert(next.end(), segment.begin(), segment.end());
45                            next.insert(next.end(), remaining.begin() + pos, remaining.end());
46
47                            // Enqueue the new state if it has not been visited yet.
48                            if (!visited.count(next)) {
49                                visited.insert(next);
50                                queue.push_back(next);
51                            }
52                        }
53                    }
54                }
55            }
56        }
57    }
58};
59

1function minSplitMerge(nums1: number[], nums2: number[]): number {
2    const n: number = nums1.length;
3
4    // Serialize an array state into a string key for the visited set.
5    const encode = (arr: number[]): string => arr.join(',');
6
7    // The target state we want to reach (as a serialized key).
8    const targetKey: string = encode(nums2);
9
10    // BFS queue (processed level by level), starting from the initial array.
11    let queue: number[][] = [nums1];
12
13    // Visited set to avoid revisiting the same array state.
14    const visited: Set<string> = new Set<string>();
15    visited.add(encode(nums1));
16
17    // BFS: 'steps' counts how many split-merge operations have been applied.
18    for (let steps = 0; ; steps++) {
19        // Take a snapshot of the current level and reset the queue
20        // so it can collect states of the next level.
21        const currentLevel: number[][] = queue;
22        queue = [];
23
24        for (const current of currentLevel) {
25            // If the current state matches the target, return the step count.
26            if (encode(current) === targetKey) {
27                return steps;
28            }
29
30            // Enumerate every subarray [left, right] to remove.
31            for (let left = 0; left < n; left++) {
32                for (let right = left; right < n; right++) {
33                    // 'remaining' is the array with the subarray removed.
34                    const remaining: number[] = [
35                        ...current.slice(0, left),
36                        ...current.slice(right + 1),
37                    ];
38
39                    // 'segment' is the removed subarray.
40                    const segment: number[] = current.slice(left, right + 1);
41
42                    // Try re-inserting the segment at every possible position.
43                    for (let pos = 0; pos <= remaining.length; pos++) {
44                        const next: number[] = [
45                            ...remaining.slice(0, pos),
46                            ...segment,
47                            ...remaining.slice(pos),
48                        ];
49
50                        // Enqueue the new state if it has not been visited yet.
51                        const nextKey: string = encode(next);
52                        if (!visited.has(nextKey)) {
53                            visited.add(nextKey);
54                            queue.push(next);
55                        }
56                    }
57                }
58            }
59        }
60    }
61}
62

Time and Space Complexity

Time complexity: O(n! × n^4), where n is the length of the array.
- The BFS explores states that are permutations (orderings) of the array elements, so the number of distinct states is bounded by n! (the visited set vis guarantees each state is processed at most once).
- For each state, the code enumerates every subarray via the two nested loops over l and r, which gives O(n^2) choices. For each subarray, it tries all O(n) insertion positions i. Constructing each new state nxt (slicing and concatenating lists, building the tuple) takes O(n) time, and the hash/lookup in vis also costs O(n).
- Therefore, the work per state is O(n^2 × n × n) = O(n^4), and the total time is O(n! × n^4).
Space complexity: O(n! × n).
- The visited set vis and the BFS queue q may store up to O(n!) states, and each state is a tuple of length n, giving O(n! × n) space in total.

Common Pitfalls

Marking States as Visited Too Late (at Dequeue Time Instead of Insertion Time)

The Pitfall

A very common mistake when writing BFS is to check and mark a state as visited only when it is popped from the queue, like this:

queue = [start]
visited = set()

for step in count(0):
    current_level = queue
    queue = []
    for state in current_level:
        if state in visited:       # checked too late!
            continue
        visited.add(state)          # marked too late!

        if state == target:
            return step

        # ... generate all next_state values ...
        queue.append(next_state)    # duplicates pile up here

Why is this a problem? Each state has roughly O(n^3) outgoing transitions, and many different (left, right, pos) choices produce the same resulting arrangement (for example, cutting [L..R] and pasting it back into its original spot is a no-op, and arrays with duplicate values collide even more often). If duplicates are only filtered when dequeued, the same state can be appended to the queue dozens of times within a single level. Across multiple levels this multiplies, and the queue can blow up combinatorially — turning a search over at most n! = 720 states into one over many thousands of redundant entries. The answer is still correct, but memory and runtime degrade badly, and on tighter limits this pattern causes TLE/MLE.

The Solution

Mark a state as visited at the moment it is generated, before appending it to the queue — exactly as the provided code does:

for pos in range(len(remaining) + 1):
    next_state = tuple(remaining[:pos] + subarray + remaining[pos:])
    if next_state not in visited:
        visited.add(next_state)     # mark immediately on generation
        queue.append(next_state)    # each state enters the queue at most once

With insertion-time deduplication, every distinct arrangement enters the queue exactly once, bounding the total work by O(n! × n^4) regardless of how many transitions collide on the same state.

A Related Trap to Watch For

If you move the target check into the neighbor-generation loop (i.e., if next_state == target: return step + 1) and remove the check on the dequeued state, you silently break the step = 0 case: when nums1 already equals nums2, the function should return 0, but the start state is never compared against the target. Always either keep the equality check on the state being processed (as in the given code), or explicitly handle nums1 == nums2 before the BFS begins:

if start == target:
    return 0

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know