We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Two Arrays Equal by Reversing Subarrays

Number: 1556

Difficulty: Easy

Paid? No

Companies: Microsoft, Meta

Problem Description

Given two integer arrays, target and arr, you are allowed to reverse any non-empty subarray in arr any number of times. Determine whether you can make arr equal to target.

Key Insights

  • Reversing subarrays allows any permutation of the array elements.
  • The only necessary condition is that target and arr must contain the same multiset of elements.
  • Use frequency counting or sorting to compare the two arrays.

Space and Time Complexity

Time Complexity: O(n log n) if sorting is used or O(n) if using frequency counting
Space Complexity: O(n)

Solution

The solution checks if the two arrays contain the same elements with the same frequencies. Since reversing subarrays can rearrange arr in any order, if the multiset of arr equals the multiset of target, then it is always possible to transform arr into target. This is accomplished by either sorting both arrays and comparing them, or by using a hash table (or dictionary) to count the frequency of elements in each array and then comparing the counts.

Code Solutions

# Python solution using sorting
def canBeEqual(target, arr):
    # Compare sorted versions of both arrays
    return sorted(target) == sorted(arr)

# Example usage:
if __name__ == "__main__":
    target = [1, 2, 3, 4]
    arr = [2, 4, 1, 3]
    print(canBeEqual(target, arr))  # Output: True
← Back to All Questions