Make Two Arrays Equal by Reversing Subarrays - Solution & Explanation
Problem Statement
You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.
Return true if you can make arr equal to target or false otherwise.
Example 1:
Input: target = [1,2,3,4], arr = [2,4,1,3] Output: true Explanation: You can follow the next steps to convert arr to target: 1- Reverse subarray [2,4,1], arr becomes [1,4,2,3] 2- Reverse subarray [4,2], arr becomes [1,2,4,3] 3- Reverse subarray [4,3], arr becomes [1,2,3,4] There are multiple ways to convert arr to target, this is not the only way to do so.
Example 2:
Input: target = [7], arr = [7] Output: true Explanation: arr is equal to target without any reverses.
Example 3:
Input: target = [3,7,9], arr = [3,7,11] Output: false Explanation: arr does not have value 9 and it can never be converted to target.
Constraints:
target.length == arr.length1 <= target.length <= 10001 <= target[i] <= 10001 <= arr[i] <= 1000
Approach Overview
Problem Overview: You are given two integer arrays target and arr. You can reverse any subarray of arr any number of times. The goal is to determine whether these operations can transform arr into target. The key observation: reversing subarrays changes order but never changes the elements themselves.
Approach 1: Sort and Compare (Time: O(n log n), Space: O(1) or O(n))
If reversing subarrays can rearrange elements arbitrarily, the only requirement for equality is that both arrays contain the same multiset of numbers. Sorting both arrays exposes this directly. Sort target and arr, then iterate once to check whether every element matches at the same index. If they match completely, you can reorder arr through subarray reversals to reach target. Sorting dominates the runtime with O(n log n) complexity, while the comparison step is O(n). Many standard library sorting implementations use O(log n) auxiliary stack space or O(n) depending on the language.
This approach is straightforward and reliable. It works well when implementation speed matters and constraints are small to medium. Since the logic is simple—sort then compare—it is often the first solution developers write during interviews.
Approach 2: Use Hashing to Count Frequencies (Time: O(n), Space: O(n))
A more optimal solution avoids sorting by counting element frequencies. Traverse target and store counts in a hash map (or frequency array if values are bounded). Then iterate through arr and decrement the corresponding count for each element. If any element appears more times than expected or is missing from the map, the arrays cannot be made equal.
This works because reversing subarrays only changes ordering, not frequency. If both arrays contain the same elements with identical counts, any permutation is achievable through a sequence of reversals. Hash table lookups and updates run in constant time on average, so the full traversal remains O(n).
This method uses concepts from hash tables and arrays. Compared with sorting, it improves runtime but uses additional memory to store counts.
Recommended for interviews: The hashing approach is typically preferred because it achieves O(n) time while clearly demonstrating understanding of element frequency comparison. The sorting solution still shows correct reasoning and knowledge of sorting, but interviewers often expect you to recognize that order is irrelevant and only counts matter.
Approach 1: Approach 1: Sort and Compare
This approach leverages the property that reversing subarrays can reorder elements but will not affect the element counts. Thus, if the sorted versions of the arrays are the same, then the arrays can be made equal.
This solution sorts both arrays and then compares them element by element.
Complexity
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) for in-place sort.
Approach 2: Approach 2: Use Hashing to Count Frequencies
Instead of sorting, we can simply count the occurrences of each element in both arrays. If the frequency distributions are the same, the arrays can be made equal.
This solution uses an array to count occurrences of each element, incrementing for elements of target and decrementing for arr.
Complexity
Time complexity: O(n) for a single pass through the arrays.
Space complexity: O(1) as the frequency array size is constant.
Approach 3: Sorting
If two arrays are equal after sorting, then they can be made equal by reversing sub-arrays.
Therefore, we only need to sort the two arrays and then check if the sorted arrays are equal.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
PHP
C
Approach 4: Counting
We note that the range of the array elements given in the problem is 1 \sim 1000. Therefore, we can use two arrays cnt1 and cnt2 of length 1001 to record the number of times each element appears in the arrays target and arr respectively. Finally, we just need to check if the two arrays are equal.
We can also use only one array cnt. We traverse the arrays target and arr. For target[i], we increment cnt[target[i]], and for arr[i], we decrement cnt[arr[i]]. In the end, we check if all elements in the array cnt are 0.
The time complexity is O(n + M), and the space complexity is O(M). Here, n is the length of the array arr, and M is the range of the array elements. In this problem, M = 1001.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare | Time complexity: O(n log n) due to sorting. |
| Approach 2: Use Hashing to Count Frequencies | Time complexity: O(n) for a single pass through the arrays. |
| Sorting | — |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n log n) | O(1) to O(n) | Simple implementation when sorting cost is acceptable |
| Hash Frequency Counting | O(n) | O(n) | Optimal solution when linear time comparison is preferred |
Video Solution
Make Two Arrays Equal by Reversing Subarrays - Leetcode 1460 - Python • NeetCodeIO • 9,489 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Two Arrays Equal by Reversing Subarrays easy or hard?
Make Two Arrays Equal by Reversing Subarrays Python/Java solution
How to solve Make Two Arrays Equal by Reversing Subarrays in O(n)?
What is the best approach for Make Two Arrays Equal by Reversing Subarrays?
Is Make Two Arrays Equal by Reversing Subarrays asked at Google/Amazon/Meta?
What data structure is used in Make Two Arrays Equal by Reversing Subarrays?
What is the time complexity of Make Two Arrays Equal by Reversing Subarrays?
Ready to solve this problem?
Practice Make Two Arrays Equal by Reversing Subarrays with our built-in code editor and test cases.
Practice on FleetCode