This post is part of the Algorithms Problem Solving series.

## Problem description

This is the Equal Reversed Arrays problem. The description looks like this:

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array 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.

## Examples

```
Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Input: target = [7], arr = [7]
Output: true
Input: target = [1,12], arr = [12,1]
Output: true
```

## Solution

As I can reverse as many subarray as I need, my first idea was to just sort the two arrays and compare the values.

```
def can_be_equal(target, arr):
return target == arr or sorted(target) == sorted(arr)
```

I just added a logic before trying to sort: if they have the same values, return true. Otherwise, sort and compare.

This solution is `O(NlogN)`

as the sort algorithm has this complexity.

Another approach is to count the elements of each array in a hash map. The key is the item and the value is the counter. In the end, if the counter is even, it is because both arrays have the same item.

```
def can_be_equal(target, arr):
counter = {}
for index in range(len(target)):
target_item, arr_item = target[index], arr[index]
if target_item in counter:
counter[target_item] += 1
else:
counter[target_item] = 1
if arr_item in counter:
counter[arr_item] += 1
else:
counter[arr_item] = 1
for _, value in counter.items():
if value % 2 != 0:
return False
return True
```

Here we are iterating through the arrays (`O(N)`

) and through the hash map (`O(N)`

), so the runtime complexity is `O(N)`

. But now we use a map, so the space complexity is `O(N)`

for the worst-case scenario.

Just to make it a better solution in Python, we can use the `Counter`

class from the collections module. It counts each item and add to the hash map as we did in the algorithm above, but with a one liner code.

```
def can_be_equal(target, arr):
return collections.Counter(target) == collections.Counter(arr)
```

## Resources

- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course

## Top comments (0)