Algorithms Problem Solving: Equal Reversed Arrays
Tags: algorithms, python, computerscience, interview
Published: 2020-06-04 11:07:54

---
title: Algorithms Problem Solving: Equal Reversed Arrays
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/equality.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/equal-reversed-arrays.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem description

This is the [Equal Reversed Arrays](https://leetcode.com/problems/make-two-arrays-equal-by-reversing-sub-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

```tsx
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.

```python
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.

```python
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.

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

## Resources

- [Learning Python: From Zero to Hero](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)