Equal Reversed Arrays
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
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!