Make Two Arrays Equal by Reversing Subarrays

Make Two Arrays Equal by Reversing Subarrays

What is this problem about?

You are given two integer arrays of equal length, target and arr. You are allowed to select any non-empty subarray of arr and reverse it. You can perform this operation any number of times. You need to determine if it is possible to make arr exactly equal to target.

Why is this asked in interviews?

This is a classic "trick" question that assesses a candidate's understanding of array permutations. Interviewers ask it to see if a candidate will attempt to actually simulate the subarray reversals, or if they possess the mathematical insight to realize that unlimited subarray reversals allow for any possible permutation of the array (similar to how Bubble Sort swaps adjacent elements).

Algorithmic pattern used

This problem requires zero simulation; it is a pure Sorting / Hash Map (Frequency Counting) pattern. Because you can reverse any subarray of length 2, you can effectively swap any two adjacent elements. Since you can swap any two adjacent elements infinitely, you can completely sort the array or rearrange it into any permutation. Therefore, arr can be made equal to target if and only if arr and target contain the exact same elements with the exact same frequencies.

Example explanation

Target: [1, 2, 3, 4], Arr: [2, 4, 1, 3] Can we make them equal? Instead of trying to find the sequence of reversals:

1. Reversing [4, 1] makes it [1, 4]. Now array is [2, 1, 4, 3].
2. Reversing [2, 1] makes it [1, 2]. Now array is [1, 2, 4, 3].
3. Reversing [4, 3] makes it [3, 4]. Now array is [1, 2, 3, 4]. We didn't need to do that! We just need to check if the arrays have the same elements. Sort Target: [1, 2, 3, 4]. Sort Arr: [1, 2, 3, 4]. They match! Return true.

Common mistakes candidates make

The absolute biggest mistake is trying to write a BFS or DFS to find the exact sequence of reversals to transform arr into target. This demonstrates a lack of foundational sorting theory and will immediately Time Limit Exceed. The problem doesn't ask how many steps or what steps; it only asks if it's possible.

Interview preparation tip

When an interview question asks "can you make A equal to B by swapping or reversing adjacent elements/subarrays?", it is almost always asking "are A and B anagrams/permutations of each other?" Simply dump both arrays into a Hash Map to count frequencies, or sort both arrays and compare them.