#1460

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Make Two Arrays Equal by Reversing Subarrays

Solve Make Two Arrays Equal by Reversing Subarrays by checking whether target and arr contain the same values with matching counts.

array hash table sorting

Problem Statement

You are given two integer arrays, target and arr, with the same length. In one move, you may choose any non-empty contiguous part of arr and reverse it. You can repeat this operation as many times as needed, and the goal is to decide whether arr can be transformed so its final order matches target exactly.

Instead of tracking specific reversals, focus on what reversals preserve and what they can change. Reversing subarrays can move values around freely enough that order stops being the limiting factor, but value counts still matter. If arr is missing a number that target needs, or contains a different frequency for any number, the transformation is impossible.

Examples

Example 1

Input: target = [1,2,3,4], arr = [2,4,1,3]

Output: true

You can follow the next steps to convert arr to target: 1- Reverse subarray [2,4,1], arr becomes [1,4,2,3] 2- Reverse subarray [4,2], arr becomes [1,2,4,3] 3- Reverse subarray [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

arr is equal to target without any reverses.

Example 3

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

Output: false

arr does not have value 9 and it can never be converted to target.

Constraints

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

Solution Approach

Reduce the operation to a multiset check

For this problem, reversing subarrays looks like an ordering task, but the useful invariant is simpler: reversals never create or remove values. Because repeated reversals can reorder elements broadly, arr can match target if and only if both arrays contain the same numbers with the same frequencies.

Scan arrays with hash lookup counts

Build a frequency map while scanning target, then scan arr and decrement those counts. If a value in arr was never needed, or its count drops below zero, return false immediately. After both scans, every count should be zero, which confirms that each target element had a matching occurrence in arr.

Know when sorting is acceptable but not optimal

Sorting both arrays also works because equal sorted results imply equal multisets, but it adds an O(N log N) cost that is unnecessary here. The hash-based scan matches the intended Array plus Hash Table pattern and catches the exact failure mode of this problem: mismatched counts, not bad reversal choices.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Using a hash map or counting array, you process each element once while tracking frequencies, so the time complexity is O(N) and the extra space is O(N). This fits the problem better than sorting because the only thing you need to verify is whether target and arr have the same value counts.

What Interviewers Usually Probe

They want you to stop simulating reversals and explain why order is not the real constraint in this problem.
They expect you to notice that every element in target must have a matching occurrence in arr, including duplicates.
They may ask why a sorting solution works, then push for the linear-time hash counting version.

Common Pitfalls or Variants

Common pitfalls

Comparing elements by index and trying to greedily fix positions, which ignores how powerful repeated subarray reversals are.
Checking only set membership instead of frequencies, which breaks on duplicates like target = [1,1,2] and arr = [1,2,2].
Using sorting as the main explanation without stating the deeper invariant that this problem depends on: equal multisets.

Follow-up variants

Use sorting on both arrays and compare them, which is simpler to code but slower at O(N log N).
Use a fixed-size counting array instead of a hash map because values are bounded, reducing hash overhead for this problem.
Return the first mismatched value count during the scan if an interviewer wants early failure detection rather than only a final boolean check.

FAQ

Why does Make Two Arrays Equal by Reversing Subarrays reduce to counting values?

Because reversing subarrays can reorder elements extensively, but it never changes which values exist or how many times each appears. That means the decision depends only on whether target and arr have identical frequencies for every number.

Is sorting a valid solution for this problem?

Yes. If both arrays sort to the same sequence, they contain the same multiset of values, so the answer is true. However, sorting is slower than the direct frequency-count approach.

Why is the primary pattern array scanning plus hash lookup?

You solve the problem by scanning target and arr while updating counts in a hash map or counting array. The hash lookup gives constant-time frequency checks, which directly targets the mismatch condition this problem cares about.

What is the main failure mode to watch for?

The biggest mistake is ignoring duplicates. Two arrays may contain the same distinct numbers but still be impossible to match if one value appears a different number of times.

Can I use a counting array instead of a hash map?

Yes. Since the values are bounded, a counting array works well and keeps the same O(N) time. It is often even cleaner than a hash map for this specific constraint range.

terminal

Solution

Solution 1: Sorting

If two arrays are equal after sorting, then they can be made equal by reversing sub-arrays.

1

2

3

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

Solution 2: Counting

We note that the range of the array elements given in the problem is $1 \sim 1000$. Therefore, we can use two arrays `cnt1` and `cnt2` of length $1001$ to record the number of times each element appears in the arrays `target` and `arr` respectively. Finally, we just need to check if the two arrays are equal.

1

2

3

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

Continue Practicing

#1481 least number of unique integers after k removals #1418 display table of food orders in a restaurant #1366 rank teams by votes