Domain 1EasyCORE

Make Two Arrays Equal by Reversing Sub-arrays

The problem asks us to determine whether we can transform one array `arr` into another array `target` by reversing any number of sub-arrays within `arr`. The key points are: - **Inputs**: Two integer arrays `target` and `arr` of equal length. - **Output**: A boolean value indicating whether it's possible to make `arr` equal to `target`. - **Constraints**: - Both arrays have the same length, ranging from 1 to 1000 elements. - Each element in the arrays is an integer between 1 and 1000.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1460. Make Two Arrays Equal by Reversing Sub-arrays

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 72.2%


Problem Breakdown

The problem asks us to determine whether we can transform one array arr into another array target by reversing any number of sub-arrays within arr. The key points are:

  • Inputs: Two integer arrays target and arr of equal length.
  • Output: A boolean value indicating whether it’s possible to make arr equal to target.
  • Constraints:
    • Both arrays have the same length, ranging from 1 to 1000 elements.
    • Each element in the arrays is an integer between 1 and 1000.

The implicit constraints are that reversing sub-arrays allows for any permutation of elements within arr. The tricky edge cases include:

  • Arrays with duplicate elements.
  • Arrays where the transformation is impossible due to missing or extra elements.

Intuition

A brute-force approach would involve generating all possible permutations of arr and checking if any match target. However, this approach is infeasible due to its factorial time complexity, which is impractical for arrays of length up to 1000.

The key insight is that reversing sub-arrays allows us to rearrange elements freely. Therefore, the problem reduces to checking whether both arrays contain the same elements with the same frequencies. If they do, we can always rearrange arr to match target.

Approach

To solve this problem efficiently:

  1. Sort Both Arrays: By sorting both target and arr, we can easily compare them element by element.
  2. Compare Sorted Arrays: If the sorted versions of target and arr are identical, then it is possible to make arr equal to target through a series of sub-array reversals.

This approach leverages sorting, which has a time complexity of (O(n \log n)), making it efficient for the given constraints.

Complexity Analysis

  • Time Complexity: (O(n \log n)) due to the sorting step.
  • Space Complexity: (O(1)) if we sort the arrays in place. If not, (O(n)) for storing sorted versions of the arrays.

Solution

def canBeEqual(target, arr):
    # Sort both arrays
    target.sort()
    arr.sort()
    
    # Compare sorted arrays element by element
    return target == arr

# Example usage:
print(canBeEqual([1, 2, 3, 4], [2, 4, 1, 3]))  # Output: True
print(canBeEqual([7], [7]))                    # Output: True
print(canBeEqual([1, 12], [12, 1]))            # Output: True
print(canBeEqual([3, 7, 9], [3, 7, 11]))       # Output: False
print(canBeEqual([1, 1, 1, 1, 1], [1, 1, 1, 1, 1]))  # Output: True

Edge Cases Handled

  • Single Element Arrays: The solution correctly handles arrays with a single element.
  • Arrays with Duplicates: Sorting ensures that duplicate elements are handled correctly.
  • Impossible Transformations: If arr contains elements not present in target or vice versa, the sorted comparison will fail, returning False.