Problem Overview

You are given two integer arrays target and arr of the same length n.

In one operation, you can choose any subarray of arr and reverse it.
You can perform this operation any number of times.

Return true if you can make arr equal to target, otherwise return false.

Example 1:
Input:
target = [1,2,3,4], arr = [2,4,1,3]
Output:
true
Explanation:
You can reverse the subarray [2,4,1,3] → [3,1,4,2],
then reverse another subarray [3,1] → [1,3], and after some operations you can make arr equal to target.

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

Example 3:
Input:
target = [1,12], arr = [12,1]
Output:
true
Explanation:
Just reverse the entire array [12,1] to get [1,12].

Example 4:
Input:
target = [3,7,9], arr = [3,7,11]
Output:
false
Explanation:
The element 11 in arr does not exist in target, so we can never make them equal.

---

Intuition / Approach

The key to this problem lies in understanding what reversing subarrays allows us to do.

Reversing any subarray means we can reorder the array in any possible way.
Therefore, if two arrays have the same elements with the same frequency, we can always make one equal to the other by reversing subarrays appropriately.

So, the real question becomes:

Do target and arr contain exactly the same elements with the same counts?

If yes → return true.
If no → return false.

---

Simplified Problem Restatement

You just need to check whether target and arr are permutations of each other.

---

Algorithm Explanation

We can check this in two ways:

1. Sorting Method:
   • Sort both arrays.
   • If the sorted versions are identical, return true, else false.
2. Frequency Counting Method:
   • Count how many times each number appears in target and in arr.
   • Compare these frequency counts.
   • If all counts match, return true.

Both approaches are correct. The sorting method is simpler to implement and works efficiently for typical input sizes.

We’ll implement both for clarity, starting with the sorting approach.

---

Java Code Implementation (Sorting Approach)

import java.util.Arrays;

public class MakeTwoArraysEqual {
    public boolean canBeEqual(int[] target, int[] arr) {
        // Step 1: Sort both arrays
        Arrays.sort(target);
        Arrays.sort(arr);

        // Step 2: Compare sorted arrays element by element
        return Arrays.equals(target, arr);
    }

    // Optional main method for testing
    public static void main(String[] args) {
        MakeTwoArraysEqual obj = new MakeTwoArraysEqual();

        int[] target1 = {1, 2, 3, 4};
        int[] arr1 = {2, 4, 1, 3};
        System.out.println(obj.canBeEqual(target1, arr1)); // true

        int[] target2 = {3, 7, 9};
        int[] arr2 = {3, 7, 11};
        System.out.println(obj.canBeEqual(target2, arr2)); // false

        int[] target3 = {1, 12};
        int[] arr3 = {12, 1};
        System.out.println(obj.canBeEqual(target3, arr3)); // true
    }
}

---

Dry Run Example

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

Step 1: Sort both arrays

• Sorted target: [1,2,3,4]
• Sorted arr: [1,2,3,4]

Step 2: Compare element by element → all match.

Output: true

---

Complexity Analysis

• Time Complexity:
  O(n log n)
  Sorting both arrays takes O(n log n) time. The comparison is O(n).
• Space Complexity:
  O(1) or O(n) depending on the sorting algorithm implementation (for example, merge sort uses O(n) auxiliary space).

---

Alternative Approach: Frequency Counting

Instead of sorting, we can count occurrences of each number in both arrays.

import java.util.HashMap;
import java.util.Map;

public class MakeTwoArraysEqualUsingMap {
    public boolean canBeEqual(int[] target, int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();

        // Count frequency in target
        for (int num : target) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        // Decrease frequency for elements in arr
        for (int num : arr) {
            if (!freq.containsKey(num)) return false;
            freq.put(num, freq.get(num) - 1);
            if (freq.get(num) == 0) freq.remove(num);
        }

        // If map is empty, both arrays match
        return freq.isEmpty();
    }

    public static void main(String[] args) {
        MakeTwoArraysEqualUsingMap obj = new MakeTwoArraysEqualUsingMap();
        int[] target = {1, 2, 3, 4};
        int[] arr = {2, 4, 1, 3};
        System.out.println(obj.canBeEqual(target, arr)); // true
    }
}

Explanation:

1. For every number in target, increase its count in the map.
2. For every number in arr, decrease its count.
3. If a number doesn’t exist or count mismatches, return false.
4. If the map becomes empty, both arrays have identical frequency distributions.

This avoids sorting and is more efficient for large arrays when numbers have limited range.

---

Complexity Analysis (Frequency Counting Approach)

• Time Complexity:
  O(n)
  We traverse both arrays once.
• Space Complexity:
  O(n)
  In the worst case, the frequency map stores counts for all unique elements.

---

Final Thoughts

This problem teaches that reversing subarrays gives full control over element ordering, reducing the problem to checking if two arrays are permutations of each other.

The sorting-based approach is concise and intuitive, while the frequency-based approach avoids sorting and achieves linear time complexity.

Such reasoning applies broadly to problems involving array reordering or swaps — often, the core question is about element equality and frequency, not the order itself.