Equal Reversed Arrays

2020-06-03

python algorithms_and_data_structures

Photo by Elyssa Fahndrich

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

Have fun, keep learning, and always keep coding!

My Twitter and Github