Make Two Arrays Equal by Reversing Subarrays

Difficulty: Easy | Acceptance: 75.80% | Paid: No Topics: Array, Hash Table, Sorting

You are 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.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Hash Map Frequency Count
• Approach 3: Greedy Simulation

Examples

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.

Example 2:

Input: target = [7], arr = [7]
Output: true

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false

Constraints

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

Approach 1: Sorting

Intuition Since we can reverse any subarray, we can effectively swap any two elements by reversing the subarray between them. This means we can reorder arr into any permutation we want. Therefore, arr can be made equal to target if and only if they contain the exact same elements in the same frequencies. Sorting both arrays puts them into a canonical order; if the sorted arrays are identical, the original arrays are permutations of each other.

Steps

• Create a copy of target and arr (or sort in place if allowed).
• Sort both arrays in ascending order.
• Compare the sorted arrays element by element.
• If all elements match, return true; otherwise, return false.

class Solution:
    def canBeEqual(self, target: list[int], arr: list[int]) -> bool:
        target.sort()
        arr.sort()
        return target == arr

Complexity

• Time: O(n log n) due to sorting, where n is the length of the arrays.
• Space: O(1) or O(n) depending on the sorting algorithm implementation used by the language.
• Notes: This is the most straightforward approach and is very efficient for the given constraints (n <= 1000).

Approach 2: Hash Map Frequency Count

Intuition Instead of sorting, we can count the frequency of each number in the target array. Then, we iterate through the arr array and decrement the corresponding count in the map. If we ever try to decrement a count that is zero (or missing), or if the final map contains any non-zero counts, the arrays are not equal.

Steps

• Initialize a hash map (or dictionary) to store frequencies of elements in target.
• Iterate through target and populate the frequency map.
• Iterate through arr. For each element, check if it exists in the map with a positive count. If not, return false. Otherwise, decrement the count.
• Return true if the loop completes without mismatches.

from collections import Counter

class Solution:
    def canBeEqual(self, target: list[int], arr: list[int]) -> bool:
        return Counter(target) == Counter(arr)

Complexity

• Time: O(n) since we iterate through the arrays twice and hash map operations are O(1) on average.
• Space: O(n) to store the frequency counts in the worst case where all elements are unique.
• Notes: This is theoretically faster than sorting for large n, but for n=1000, the difference is negligible.

Approach 3: Greedy Simulation

Intuition We can simulate the process of making arr equal to target. Since we can reverse any subarray, we can bring the correct element to the current position i by finding the element target[i] in arr (at some index j >= i) and reversing the subarray arr[i...j]. This effectively swaps the element at j to position i while shifting the intermediate elements.

Steps

• Iterate through the array with index i from 0 to n-1.
• If arr[i] already matches target[i], continue.
• If arr[i] does not match, find the index j (where j >= i) such that arr[j] == target[i].
• If no such j exists, return false.
• Reverse the subarray of arr from index i to j.
• After processing all indices, return true.

class Solution:
    def canBeEqual(self, target: list[int], arr: list[int]) -> bool:
        n = len(target)
        for i in range(n):
            if arr[i] != target[i]:
                # Find target[i] in the remaining part of arr
                try:
                    j = arr.index(target[i], i)
                except ValueError:
                    return False
                # Reverse subarray arr[i:j+1]
                arr[i:j+1] = arr[i:j+1][::-1]
        return True

Complexity

• Time: O(n²) in the worst case. For each element, we might scan the rest of the array (O(n)) and reverse up to O(n) elements.
• Space: O(1) extra space (modifying arr in place).
• Notes: This approach is less efficient than Sorting or Hash Map but demonstrates the mechanics of the allowed operation.