LeetCode Problem 3690

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Breadth-First Search

Solution

LeetCode 3690 - Split and Merge Array Transformation

Problem Understanding

The problem gives us two arrays, nums1 and nums2, of equal length n. We are allowed to repeatedly perform a special operation on nums1.

In a single operation, we choose any contiguous subarray, remove it from its current location, and then insert that entire subarray somewhere else in the array while preserving the order of the elements inside the moved block.

This operation is essentially a "cut and paste" operation on a contiguous segment.

Our goal is to determine the minimum number of such operations needed to transform nums1 into nums2.

The input arrays contain the same multiset of values. The statement guarantees that nums2 is a permutation of nums1, so a transformation is always possible.

The most important constraint is:

• 2 <= n <= 6

This is extremely small. Even though the operation itself can rearrange the array in many ways, the total number of distinct array configurations is limited. For example, when all elements are distinct and n = 6, there are only 6! = 720 possible permutations.

This small bound strongly suggests that a state-space search such as Breadth-First Search (BFS) is feasible.

Some important edge cases include:

• nums1 already equals nums2, in which case the answer is 0.
• Arrays containing duplicate values, where multiple different move sequences may lead to the same array.
• Cases where a single large block move solves the problem immediately.
• Cases requiring several moves despite appearing close to the target arrangement.

Because the array length is at most six, we can explicitly explore all reachable states and still remain efficient.

Approaches

Brute Force

A natural brute-force idea is to recursively try every possible split-and-merge operation from the current array and search for the target.

For each state, we can:

1. Choose every possible subarray.
2. Remove it.
3. Reinsert it at every possible position.
4. Recursively continue searching.

This approach is correct because it explores every possible sequence of operations. Eventually it will find the minimum number of moves.

The problem is that naive recursion repeatedly revisits the same array configurations many times. The search tree contains enormous duplication.

Key Insight

The operation defines a graph:

• Each distinct array configuration is a node.
• A split-and-merge operation is an edge between two nodes.
• Every edge has cost 1.

The problem asks for the minimum number of operations needed to transform one configuration into another.

That is exactly the shortest-path problem in an unweighted graph.

Breadth-First Search is the ideal algorithm because:

• BFS explores states in order of increasing distance.
• The first time we reach nums2, we are guaranteed to have used the minimum number of operations.
• The total number of states is very small because n <= 6.

We can therefore perform BFS over all reachable array configurations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Repeatedly explores the same states
Optimal BFS	O(S · n⁴)	O(S)	Explores each distinct state once

Here S denotes the number of distinct reachable array configurations, at most 6! = 720.

Algorithm Walkthrough

Step 1: Handle the trivial case

If nums1 already equals nums2, no operations are needed, so return 0.

Step 2: Represent states

Convert arrays into tuples.

Tuples are immutable and hashable, allowing them to be stored in a hash set for the BFS visited structure.

Step 3: Initialize BFS

Create:

• A queue storing (state, distance).
• A visited set containing the starting state.

The distance represents the number of split-and-merge operations used to reach that state.

Step 4: Generate all possible moves

For the current state:

1. Choose every possible pair (L, R).
2. Extract the contiguous block state[L:R+1].
3. Remove it, producing the remaining array.
4. Insert the block into every possible insertion position within the remaining array.

Each resulting array is a valid state reachable in one operation.

Step 5: Avoid revisiting states

Whenever a newly generated state appears:

• Skip it if it is already in the visited set.
• Otherwise add it to visited and enqueue it with distance current_distance + 1.

This guarantees that each state is processed only once.

Step 6: Stop when the target is found

The first time BFS reaches nums2, return the associated distance.

Because BFS explores states level by level, this distance is the minimum number of operations.

Why it works

The graph formed by all array configurations is an unweighted graph where each split-and-merge operation corresponds to one edge. BFS always explores all states reachable in k operations before exploring states reachable in k + 1 operations. Therefore, when the target state is first discovered, no shorter sequence of operations can exist. This guarantees that the returned distance is the minimum number of split-and-merge operations required.

Python Solution

from collections import deque
from typing import List, Tuple

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

        if start == target:
            return 0

        queue = deque([(start, 0)])
        visited = {start}

        n = len(nums1)

        while queue:
            state, dist = queue.popleft()

            for left in range(n):
                for right in range(left, n):
                    block = state[left:right + 1]
                    remaining = state[:left] + state[right + 1:]

                    for pos in range(len(remaining) + 1):
                        next_state = (
                            remaining[:pos]
                            + block
                            + remaining[pos:]
                        )

                        if next_state == state:
                            continue

                        if next_state in visited:
                            continue

                        if next_state == target:
                            return dist + 1

                        visited.add(next_state)
                        queue.append((next_state, dist + 1))

        return -1

The implementation follows the BFS strategy directly.

The initial state and target state are converted into tuples so they can be stored in hash-based containers. A queue maintains the BFS frontier, while a visited set prevents repeated processing of the same configuration.

For every dequeued state, the code enumerates all possible contiguous subarrays using (left, right). The chosen block is removed, producing the remaining array. The block is then inserted at every possible position, generating all states reachable in exactly one operation.

Whenever a new state is generated, it is checked against the target. Since BFS explores states in increasing order of distance, the first time the target appears we can immediately return the answer.

Go Solution

package main

func minSplitMerge(nums1 []int, nums2 []int) int {
	start := encode(nums1)
	target := encode(nums2)

	if start == target {
		return 0
	}

	type Node struct {
		state []int
		dist  int
	}

	queue := []Node{{append([]int(nil), nums1...), 0}}
	visited := map[string]bool{start: true}

	n := len(nums1)
	head := 0

	for head < len(queue) {
		cur := queue[head]
		head++

		state := cur.state

		for left := 0; left < n; left++ {
			for right := left; right < n; right++ {
				block := append([]int(nil), state[left:right+1]...)

				remaining := make([]int, 0, n-(right-left+1))
				remaining = append(remaining, state[:left]...)
				remaining = append(remaining, state[right+1:]...)

				for pos := 0; pos <= len(remaining); pos++ {
					nextState := make([]int, 0, n)

					nextState = append(nextState, remaining[:pos]...)
					nextState = append(nextState, block...)
					nextState = append(nextState, remaining[pos:]...)

					key := encode(nextState)

					if key == encode(state) {
						continue
					}

					if visited[key] {
						continue
					}

					if key == target {
						return cur.dist + 1
					}

					visited[key] = true
					queue = append(queue, Node{
						state: nextState,
						dist:  cur.dist + 1,
					})
				}
			}
		}
	}

	return -1
}

func encode(nums []int) string {
	b := make([]byte, 0)

	for _, x := range nums {
		b = append(b, []byte(string(rune(x+200000)))...)
		b = append(b, '#')
	}

	return string(b)
}

The Go implementation follows exactly the same BFS logic as the Python version.

The primary difference is that Go slices are mutable, so new slices must be explicitly created when generating successor states. A string encoding is used as the hashable key inside the visited map. Since the constraints are extremely small, this representation is more than sufficient.

Worked Examples

Example 1

Input

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

Initial BFS state:

State	Distance
[3,1,2]	0

One generated move is:

Chosen Block	Remaining	Insert Position	Result
[3]	[1,2]	End	[1,2,3]

The generated state equals the target.

State	Distance
[1,2,3]	1

Answer:

1

Example 2

Input

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

BFS begins from:

State	Distance
[1,1,2,3,4,5]	0

Level 1 explores every possible split-and-merge operation.

Level 2 explores every state reachable in two operations.

Level 3 eventually reaches:

State	Distance
[5,4,3,2,1,1]	3

Since BFS visits states in increasing distance order, the first discovery at distance 3 proves that no solution using fewer than three operations exists.

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(S · n⁴)	Each state generates O(n³) moves, each requiring O(n) construction time
Space	O(S)	Queue and visited set store each distinct state once

Here S is the number of distinct array configurations. Since n ≤ 6, we have:

S ≤ 6! = 720

The actual running time is therefore very small. Even exploring every possible state is easily feasible within the problem constraints.

Test Cases

sol = Solution()

assert sol.minSplitMerge([3, 1, 2], [1, 2, 3]) == 1  # example 1

assert sol.minSplitMerge(
    [1, 1, 2, 3, 4, 5],
    [5, 4, 3, 2, 1, 1]
) == 3  # example 2

assert sol.minSplitMerge([1, 2], [1, 2]) == 0  # already equal

assert sol.minSplitMerge([1, 2], [2, 1]) == 1  # move one element

assert sol.minSplitMerge([1, 2, 3], [2, 3, 1]) == 1  # move prefix to end

assert sol.minSplitMerge([1, 2, 3], [3, 1, 2]) == 1  # move suffix to front

assert sol.minSplitMerge([1, 1, 2], [1, 2, 1]) == 1  # duplicates

assert sol.minSplitMerge([1, 2, 3, 4], [4, 3, 2, 1]) >= 1  # reversal

assert sol.minSplitMerge([-1, 0, 1], [1, -1, 0]) == 1  # negative values

assert sol.minSplitMerge([1, 2, 3, 4, 5, 6], [6, 5, 4, 3, 2, 1]) >= 1  # max length distinct

Test Summary

Test	Why
[3,1,2] -> [1,2,3]	Official example
[1,1,2,3,4,5] -> [5,4,3,2,1,1]	Official example
Identical arrays	Verifies zero operations
[1,2] -> [2,1]	Smallest nontrivial case
Prefix moved to end	Single block movement
Suffix moved to front	Another single move pattern
Duplicate values	Ensures state handling is correct
Length 4 reversal	Multiple possible paths
Negative numbers	Value range handling
Length 6 distinct values	Maximum-size state space

Edge Cases

Arrays Already Match

When nums1 and nums2 are identical, the answer must be zero. A common bug is to start BFS immediately and return one after generating a self-transition. The implementation avoids this by checking equality before beginning the search.

Duplicate Values

Arrays may contain repeated numbers. Different move sequences can generate the same array configuration. If states are not tracked correctly, BFS may revisit identical configurations many times. Using tuple-based state representations and a visited set guarantees that each distinct configuration is processed only once.

Moving the Entire Array

The chosen subarray may be the entire array. Removing and reinserting the entire array produces the same state. Such transitions are useless and can create redundant work. The implementation explicitly skips successor states that are identical to the current state.

Maximum State Space

When all six elements are distinct, the number of reachable configurations is largest. A solution based on exhaustive recursive search may perform excessive repeated work. BFS with a visited set ensures that each configuration is explored at most once, keeping the search efficient even in the worst case.