Code Implementation

from collections import Counter

class Solution:
    def canBeEqual(self, target, arr):
        return Counter(target) == Counter(arr)
      

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> count;
        for (int num : target) count[num]++;
        for (int num : arr) count[num]--;
        for (auto it : count) {
            if (it.second != 0) return false;
        }
        return true;
    }
};
      

import java.util.HashMap;

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int num : target) count.put(num, count.getOrDefault(num, 0) + 1);
        for (int num : arr) count.put(num, count.getOrDefault(num, 0) - 1);
        for (int val : count.values()) {
            if (val != 0) return false;
        }
        return true;
    }
}
      

var canBeEqual = function(target, arr) {
    const count = {};
    for (let num of target) count[num] = (count[num] || 0) + 1;
    for (let num of arr) count[num] = (count[num] || 0) - 1;
    for (let key in count) {
        if (count[key] !== 0) return false;
    }
    return true;
};
      

Problem Description

You are given two integer arrays, target and arr, both of the same length. Your task is to determine if it is possible to make arr equal to target by performing any number of subarray reversals on arr.

• A subarray reversal means you can select any contiguous subarray (of any length) in arr and reverse its elements in place.
• Each element in arr and target must be used exactly once; you cannot add or remove elements.
• You may perform as many subarray reversals as you like (including zero).
• The arrays may contain duplicate values.

The goal is to decide if, after some sequence of allowed reversals, arr can be made exactly equal to target.

Thought Process

At first glance, the problem seems to require simulating all possible subarray reversals, which would be very inefficient. However, let's consider what subarray reversals allow us to do.

• Reversing a subarray is a powerful operation—by chaining enough reversals, you can rearrange the array in any order you wish.
• This means the only thing that matters is whether arr contains the same elements as target, with the same frequencies.
• So instead of simulating reversals, we just need to check if the two arrays are permutations of each other.

This insight dramatically simplifies the problem from a complicated simulation to a simple comparison of element counts.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Count Elements: For both target and arr, count how many times each value appears. This can be done using a hash map (dictionary) where the key is the number and the value is its count.
2. Compare Counts: Compare the two hash maps. If every value has the same count in both arrays, then arr can be rearranged (using reversals) to match target.
3. Return the Result: Return true if the counts match, otherwise false.

Why use a hash map? Looking up and updating counts is fast (O(1) on average), making this approach efficient even for large arrays.

Alternative: You could also sort both arrays and compare them, as sorting brings equal elements together, but counting is often faster and doesn't require rearranging the input.

Example Walkthrough

Let's consider this example:

• target = [1,2,3,4]
• arr = [2,4,1,3]

Step 1: Count the elements in both arrays:

• target: 1→1, 2→1, 3→1, 4→1
• arr: 2→1, 4→1, 1→1, 3→1

Step 2: Compare the counts:

• Both arrays have exactly one of each value: 1, 2, 3, 4.

Step 3: Since the counts match, it is possible to rearrange arr into target using subarray reversals. The answer is true.

Time and Space Complexity

• Brute-force Approach: Trying all possible sequences of subarray reversals would be factorial time (O(n!)), which is impractical for even modest input sizes.
• Optimized Approach: Counting elements in both arrays is O(n), where n is the length of the arrays. Comparing two hash maps is also O(n) in the worst case.
• Space Complexity: We use O(n) extra space for the hash maps (at most one entry per unique element).

Thus, the optimized approach is both fast and memory-efficient.

Summary

The key insight in this problem is recognizing that subarray reversals allow for any permutation of the array. This reduces the challenge to checking whether the two arrays contain the same elements with the same frequencies. By using hash maps (or sorting), we can efficiently compare the arrays and determine if one can be transformed into the other. This approach is elegant because it simplifies a seemingly complex problem into a straightforward check.