Make Two Arrays Equal By Reversing Subarrays - Leetcode Solution

Problem:

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array 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 sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [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.

Solution:

To solve this problem, we need to check if the target array can be converted to the given array by reversing any of its sub-arrays any number of times.

We can achieve this by checking if both of the arrays have the same elements and the same count. To check if both arrays have the same elements, we can create a hash table for both arrays and count the frequency of each element. If the frequency of each element is the same in both arrays, then both arrays have the same elements.

Now, we need to check if we can convert the given array to the target array by reversing any of its sub-arrays. We can do this by checking if the elements between the same indexes in both arrays are the same. If the elements are not the same, we need to reverse the sub-array in the given array. Then, we can check if the elements between the same indexes in both arrays are the same. If they are not the same, then it is not possible to convert the given array to the target array.

If all the elements between the same indexes in both arrays are the same, then it is possible to convert the given array to the target array by reversing any of its sub-arrays. Therefore, we can return True.

Code:

def canBeEqual(target, arr):
    # check if both arrays have the same elements and the same count
    count1 = {}
    count2 = {}
    for i in range(len(target)):
        count1[target[i]] = count1.get(target[i], 0) + 1
        count2[arr[i]] = count2.get(arr[i], 0) + 1
    if count1 != count2:
        return False
    
    # check if we can convert the given array to the target array by reversing any of its sub-arrays
    for i in range(len(target)):
        if target[i] != arr[i]:
            j = i+1
            while j<len(target) and target[j]!=arr[i]:
                j += 1
            if j == len(target):
                return False
            arr[i:j+1] = arr[i:j+1][::-1]
    
    return True

Complexity Analysis:

Time Complexity: O(n^2), where n is the length of the array. We traverse the array two times, and we reverse the sub-array in the second traversal, which takes O(n) time. Therefore, the overall time complexity is O(n^2).

Space Complexity: O(n), where n is the length of the array. We create two hash tables for both arrays, which takes O(n) space. Therefore, the overall space complexity is O(n).

1