1460. Make Two Arrays Equal by Reversing Subarrays

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray 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.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

• target.length == arr.length
• 1 <= target.length <= 1000
• 1 <= target[i] <= 1000
• 1 <= arr[i] <= 1000

Approach 01:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // Helper function to get the frequency dictionary of elements in a vector
    unordered_map<int, int> get_dict(const vector<int>& data) {
        unordered_map<int, int> data_dict;
        for (int t : data) {
            // If the element t is not in the dictionary, initialize its count to 1
            // Otherwise, increment its count by 1
            if (data_dict.find(t) == data_dict.end()) {
                data_dict[t] = 1;
            } else {
                data_dict[t]++;
            }
        }
        return data_dict;
    }

    // Function to check if target can be made equal to arr by shuffling
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        // Get frequency dictionaries for both target and arr
        unordered_map<int, int> target_dict = get_dict(target);
        unordered_map<int, int> arr_dict = get_dict(arr);

        // Iterate through the frequency dictionary of target
        for (const auto& pair : target_dict) {
            int key = pair.first;
            int val = pair.second;
            // If key is not present in arr or its count does not match in both dictionaries, return false
            if (arr_dict.find(key) == arr_dict.end() || arr_dict[key] != val) {
                return false;
            }
        }
        
        // If all keys match with their counts, return true
        return true;
    }
};

from typing import List
from collections import defaultdict

class Solution:
    # Helper function to get the frequency dictionary of elements in a list
    def get_dict(self, data: List[int]) -> dict:
        data_dict = defaultdict(int)
        for t in data:
            data_dict[t] += 1
        return data_dict

    # Function to check if target can be made equal to arr by shuffling
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        # Get frequency dictionaries for both target and arr
        target_dict = self.get_dict(target)
        arr_dict = self.get_dict(arr)

        # Iterate through the frequency dictionary of target
        for key, val in target_dict.items():
            # If key is not present in arr or its count does not match in both dictionaries, return False
            if key not in arr_dict or arr_dict[key] != val:
                return False
        
        # If all keys match with their counts, return True
        return True

Time Complexity

• Creating Frequency Dictionaries:

  We iterate over each element of the target and arr vectors to create their frequency dictionaries. This takes \( O(n) \) time for each vector, where \( n \) is the number of elements in the vectors.

• Comparing Frequency Dictionaries:

  We then iterate over the frequency dictionary of target and perform constant-time operations for each element to compare with arr‘s frequency dictionary. This also takes \( O(n) \) time in the worst case.

• Overall Time Complexity:

  Combining both operations, the overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  We use two unordered maps to store the frequency dictionaries of target and arr. Each map can store up to \( n \) elements, where \( n \) is the number of unique elements in the vectors. Therefore, the space complexity for the maps is \( O(n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).

Approach 02:

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        return unordered_multiset<int>(arr.begin(), arr.end()) == unordered_multiset<int>(target.begin(), target.end());
    }
};

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return collections.Counter(arr) == collections.Counter(target)

Time Complexity

• Creating Multisets:

  We create an unordered_multiset for both arr and target. Constructing each multiset takes \( O(n) \) time, where \( n \) is the number of elements in the vectors.

• Comparing Multisets:

  Comparing two multisets for equality also takes \( O(n) \) time as it involves checking the frequency of each element in both multisets.

• Overall Time Complexity:

  Combining both operations, the overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  We use two unordered_multisets to store the elements of target and arr. Each multiset can store up to \( n \) elements, where \( n \) is the number of elements in the vectors. Therefore, the space complexity for the multisets is \( O(n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).