💬 Discord
Sign In
NeetCode #815LC-1460EasyGreedy
← Back to All Problems

#815 · #1460 · Make Two Arrays Equal by Reversing Subarrays(通过翻转子数组使两个数组相等)

📌 Problem Statement & Constraints

You are given two integer arrays target and arr of the same length. In one operation you may reverse any contiguous subarray of arr. Return true if it is possible to make arr equal to target. Constraints: 1 <= target.length == arr.length <= 1000, 1 <= target[i], arr[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Reversing subarrays generates exactly the permutations of arr, so any permutation of arr is reachable.
  2. Therefore arr can be made equal to target if and only if the two arrays are permutations of each other.
  3. That is equivalent to having identical multisets of values.
  4. Counting frequencies (or sorting both arrays) decides this in linear or n log n time.

💻 Benchmark Python3 Implementation

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


# Sorting variant: identical multisets sort to identical arrays
class Solution2:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(target) == sorted(arr)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) expected with the counter; O(n log n) with the sort.
💾 Space Complexity
O(n) for the counter or the sorted copies.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the reversal must be contiguous in the original order: arbitrary reversals compose into arbitrary permutations, so contiguity is not a restriction.
  • Comparing positions: order is irrelevant here; only the multiset matters.
  • Assuming values are distinct: duplicates are allowed, so a set comparison would be wrong.
  • Building a permutation-matching argument: there is no need for one; the multiset test is both necessary and sufficient.