1460. Make Two Arrays Equal by Reversing Subarrays
Description
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.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000
Solutions
Solution 1: 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$.
1 2 3 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 |
|
1 2 3 4 5 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Solution 2: 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$.