Skip to main content
Talentd

Split and Merge Array Transformation - Solution & Explanation

MediumArrayHash TableBreadth-First Search10 min readAsked at: Meta
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given an array and a set of allowed operations that split elements or merge adjacent elements. The goal is to determine whether one configuration can be transformed into another using these operations. Each transformation creates a new array state, so the task becomes exploring valid states efficiently without revisiting duplicates.

Approach 1: Brute Force State Simulation (Exponential Time, High Space)

The most direct idea is to simulate every possible sequence of split and merge operations. At each step, iterate through the array, attempt all valid splits and merges, and generate new arrays. This quickly explodes because each operation creates multiple branches. Without tracking visited states, the same configuration appears repeatedly. Time complexity grows exponentially with the number of operations, and space complexity is also exponential due to storing intermediate states.

Approach 2: Breadth-First Search with Hash Set (Optimal BFS Traversal)

Treat each array configuration as a node in a graph. An edge exists between two nodes if one can be obtained from the other via a single split or merge operation. Use Breadth-First Search to explore states level by level starting from the initial array. Each generated configuration is encoded (for example as a string or tuple) and stored in a visited hash table to prevent reprocessing duplicates.

During BFS, generate neighbors by iterating through the array and applying valid split or merge operations. Push unseen states into a queue. If the target configuration appears, the transformation is possible. BFS guarantees the shortest sequence of operations if the problem asks for minimum steps. Time complexity depends on the number of reachable states but is typically expressed as O(S * N), where S is the number of unique states explored and N is the array length. Space complexity is O(S) for the queue and visited set.

This approach works well because each state is processed once and duplicate configurations are eliminated using hashing. Arrays are naturally modeled as nodes in a state graph, making BFS the most natural traversal strategy when exploring transformation sequences involving arrays.

Recommended for interviews: Start by explaining the brute force simulation to demonstrate understanding of the operations and the search space. Then transition to the BFS state‑graph model with a visited hash set. Interviewers usually expect the BFS approach because it systematically explores transformations while avoiding repeated work.

Solution

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 q to store the current array states, and use a set vis to record the visited array states to avoid duplicate computations. Initially, the queue contains only the array nums1.

Then, we perform the following steps:

  1. Remove the current array state cur from the queue.
  2. If cur equals the target array nums2, return the current number of operations.
  3. Otherwise, enumerate all possible split positions (l, r), remove the subarray cur[l..r] to obtain the remaining array remain and the subarray sub.
  4. Insert the subarray sub into all possible positions of the remaining array remain to generate new array states nxt.
  5. If a new array state 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationExponentialExponentialUseful for understanding all possible operations or when constraints are extremely small
BFS with Hash Set (State Graph)O(S * N)O(S)General case where many transformations exist and duplicate states must be avoided
BFS with PruningO(S * N)O(S)When additional constraints allow pruning impossible states early

Video Solution

Split and Merge Array Transformation | LeetCode 3690 | Weekly Contest 468 • Sanyam IIT Guwahati • 2,243 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Split and Merge Array Transformation easy or hard?
Split and Merge Array Transformation is typically classified as a Medium difficulty problem. The operations themselves are straightforward, but recognizing the state-space search and implementing BFS with proper state encoding and deduplication adds complexity.
Split and Merge Array Transformation Python/Java solution
Implement the BFS approach by storing the starting array in a queue and generating new arrays through valid split and merge operations. Encode each array state as a tuple (Python) or string (Java) to store in a hash set for fast duplicate detection. Continue exploring until the target configuration is found or all states are exhausted.
How to solve Split and Merge Array Transformation in O(n)?
A strict O(n) solution generally does not exist because the problem requires exploring multiple transformation states. The closest practical approach is BFS with hashing, which avoids revisiting duplicate arrays. By pruning repeated states and invalid transitions, the search becomes manageable for typical constraints.
What is the best approach for Split and Merge Array Transformation?
The most effective approach models the problem as a state graph and uses Breadth-First Search (BFS). Each array configuration is treated as a node, and split or merge operations generate neighboring states. A hash set stores visited configurations to avoid duplicates. This ensures every reachable configuration is processed at most once.
Is Split and Merge Array Transformation asked at Google/Amazon/Meta?
Array transformation problems combined with BFS state exploration frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involve transforming strings, arrays, or graphs using minimal operations. The key skill being tested is recognizing the state-space search pattern and applying BFS efficiently.
What data structure is used in Split and Merge Array Transformation?
The core data structures are a queue for BFS traversal and a hash set for tracking visited states. Arrays represent the state itself, often encoded as tuples or strings for hashing. This combination ensures fast lookup and systematic exploration of transformation steps.
What is the time complexity of Split and Merge Array Transformation?
The BFS solution runs in O(S * N) time, where S is the number of unique array states explored and N is the array length. Each state requires generating possible split and merge operations across the array. Space complexity is O(S) because the queue and visited set store explored configurations.

Ready to solve this problem?

Practice Split and Merge Array Transformation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays