# Make Two Arrays Equal by Reversing Subarrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/make-two-arrays-equal-by-reversing-subarrays
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
You are given two integer arrays of equal length `target` and `arr`. In one step, you can select any **non-empty subarray** of `arr` and reverse it. You are allowed to make any number of steps.

Return `true` _if you can make_ `arr` _equal to_ `target` _or_ `false` _otherwise_.

**Example 1:**

**Input:** target = [1,2,3,4], arr = [2,4,1,3]
**Output:** true
**Explanation:** 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
**Explanation:** arr is equal to target without any reverses.

**Example 3:**

**Input:** target = [3,7,9], arr = [3,7,11]
**Output:** false
**Explanation:** 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`

# Approaches
## Sorting Approach
The fundamental insight is that the ability to reverse any subarray allows for the complete reordering of the elements in `arr`. This means `arr` can be transformed into `target` if and only if `arr` is a permutation of `target`—that is, they contain the same elements with the same frequencies. A straightforward way to verify this is to sort both arrays. If they are permutations of each other, their sorted versions will be identical.
**Time:** O(N log N), where N is the number of elements in the arrays. The dominant operation is sorting both arrays. · **Space:** O(log N) to O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types is implemented using a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack. In the worst case, it can take `O(N)` space.
**Pros:** Simple to conceptualize and implement.; The code is very concise, especially when using built-in library functions.
**Cons:** The time complexity of `O(N log N)` is less efficient than linear time solutions.; Modifies the input arrays unless copies are made, which would increase space usage.
### Explanation
This approach leverages standard sorting algorithms to check for equivalence. 

1.  The `target` array is sorted in non-decreasing order.
2.  The `arr` array is also sorted in non-decreasing order.
3.  After sorting, if the original arrays contained the same set of numbers, their sorted versions must be identical. We can then compare the two sorted arrays element by element. 
4.  A convenient way to perform this comparison in Java is by using the `Arrays.equals()` method, which returns `true` if two arrays are of the same length and all corresponding pairs of elements are equal.

```java
import java.util.Arrays;

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) {
            return false;
        }
        Arrays.sort(target);
        Arrays.sort(arr);
        return Arrays.equals(target, arr);
    }
}
```
### Algorithm
- Sort the `target` array.
- Sort the `arr` array.
- Compare the two sorted arrays. If they are identical, return `true`. Otherwise, return `false`.

## Hash Map Frequency Counting
Instead of sorting, we can verify that the arrays are permutations by counting the frequency of each element. If both arrays have the same count for every number present, they are permutations. A hash map is a suitable data structure for this task, as it can efficiently map each number to its frequency.
**Time:** O(N), where N is the length of the arrays. We perform two separate passes through the arrays, and hash map operations take, on average, O(1) time. · **Space:** O(K), where K is the number of unique elements. In the worst case, all N elements are unique, making the space complexity `O(N)`.
**Pros:** Achieves a linear time complexity of `O(N)`, which is more efficient than sorting for large N.; Flexible and works for any range of integer values, not just small, constrained ones.
**Cons:** Requires extra space for the hash map, which can be up to `O(N)` in the worst case.; Slightly more complex to implement than the sorting approach.; Can have higher constant overhead than using a simple array due to hashing.
### Explanation
This method involves two passes over the arrays.

1.  First, we create a hash map. We iterate through the `target` array, and for each number, we store or update its frequency in the map. For example, if `target` is `[1, 2, 2]`, the map will become `{1: 1, 2: 2}`.
2.  Second, we iterate through the `arr` array. For each number in `arr`, we check its status in the map. 
    - If the number is not a key in the map or its count is 0, it means `arr` has an element that `target` doesn't have, or has it in a higher frequency. We can immediately conclude they are not permutations and return `false`.
    - Otherwise, we decrement the count for that number in the map.
3.  If we successfully complete the iteration over `arr` without returning `false`, it confirms that every element in `arr` had a corresponding element in `target`, and thus the arrays are permutations. We return `true`.

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

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) {
            return false;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : target) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        for (int num : arr) {
            if (!counts.containsKey(num) || counts.get(num) == 0) {
                return false;
            }
            counts.put(num, counts.get(num) - 1);
        }
        
        return true;
    }
}
```
### Algorithm
- Create a `HashMap` to store the frequency of each number in the `target` array.
- Iterate through `target` and populate the frequency map.
- Iterate through `arr`. For each number, decrement its count in the map.
- If a number from `arr` is not in the map or its count is already zero, return `false` immediately.
- If the loop completes, it means the arrays are permutations, so return `true`.

## Array as a Frequency Counter
This approach is an optimization of the frequency counting method. Given the problem's constraint that all numbers are between 1 and 1000, we can use a simple array as a direct-access table instead of a hash map. This eliminates the overhead of hashing and object creation, making it the most efficient solution in terms of both time and space.
**Time:** O(N + M), where N is the length of the arrays and M is the range of possible values (1001). Since M is a constant, the complexity simplifies to `O(N)`. · **Space:** O(1). We use an array of a fixed size (1001) based on the problem's constraints on element values. This space usage does not scale with the input array length N.
**Pros:** Optimal time complexity of `O(N)`.; Optimal space complexity of `O(1)`, as the `counts` array size is constant and does not depend on the input size N.; Extremely fast in practice due to the use of array indexing instead of hash map operations.
**Cons:** This approach is only suitable when the range of values in the input is known and small enough to be used as array indices.
### Explanation
The core idea remains the same: check if the arrays are permutations by comparing element frequencies. 

1.  We create an integer array, `counts`, of size 1001 (to accommodate numbers from 1 to 1000) and initialize it with zeros.
2.  We can process both arrays in a single loop. For each index `i`, we treat the appearance of `target[i]` as a credit and the appearance of `arr[i]` as a debit. We do this by incrementing `counts[target[i]]` and decrementing `counts[arr[i]]`.
3.  If the two arrays are permutations, then for any number `x`, it must appear the same number of times in `target` as in `arr`. Therefore, after the loop, the net count for `x` in our `counts` array should be zero. 
4.  We perform a final check by iterating through the `counts` array. If any entry is not zero, it signifies a mismatch in frequencies, and we return `false`.
5.  If all counts are zero, it confirms the arrays are permutations, and we return `true`.

```java
class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) {
            return false;
        }
        int[] counts = new int[1001];
        for (int i = 0; i < target.length; i++) {
            counts[target[i]]++;
            counts[arr[i]]--;
        }
        
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 1001, initialized to zeros.
- Iterate through the input arrays from `i = 0` to `N-1`.
- In each iteration, increment the count for the `target` element (`counts[target[i]]++`) and decrement the count for the `arr` element (`counts[arr[i]]--`).
- After the loop, iterate through the `counts` array. If any value is non-zero, return `false`.
- If all counts are zero, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean canBeEqual(int[] target, int[] arr) {
    Arrays.sort(target);
    Arrays.sort(arr);
    return Arrays.equals(target, arr);
  }
}

```

### JavaScript

```javascript
function canBeEqual ( target , arr ) { target . sort (); arr . sort (); return target . every (( x , i ) => x === arr [ i ]); }
```

### CPP

```cpp
class Solution {
public:
  bool canBeEqual(vector<int> &target, vector<int> &arr) {
    sort(target.begin(), target.end());
    sort(arr.begin(), arr.end());
    return target == arr;
  }
};

```

### Python

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

```