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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) for in-place sort.
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(n) for a single pass through the arrays.
Space complexity: O(1) as the frequency array size is constant.
| 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. |
Make Two Arrays Equal by Reversing Subarrays - Leetcode 1460 - Python • NeetCodeIO • 8,980 views views
Watch 9 more video solutions →Practice Make Two Arrays Equal by Reversing Subarrays with our built-in code editor and test cases.
Practice on FleetCode