Vultr DocsLatest Content

Make Two Arrays Equal by Reversing Subarrays

Updated on 13 June, 2025
Make Two Arrays Equal by Reversing Subarrays header image

Problem Statement

The problem presents two integer arrays, target and arr, both of which have the same length. You are allowed to modify the array arr by reversing any non-empty subarray multiple times. The goal is to determine if it is possible to transform arr into exactly matching target through any number of such reversals. The function should return true if it's possible to make arr equal to target, and false otherwise.

Examples

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 and Intuition

To tackle this problem, it's beneficial to understand the nature of reversing operations:

  1. Reversing a subarray doesn’t change the overall composition of the array; rather, it rearranges its elements. Thus, if two arrays contain the same elements in any order, one can be rearranged to match the other using the allowed operations.

Given this principle, we can approach the problem using the following steps:

  1. Check for Equal Length: Since we know from the constraints that both arrays are of equal length, this step is inherently satisfied.

  2. Count Elements: Ensure that both target and arr have the exact same elements in the exact same frequencies. We can use a hashtable (or dictionary in Python) to count occurrences of each element in both arrays.

    • If at any point, an element's frequency in arr doesn't match its frequency in target, return false.

  3. Return True if Valid: If the element counts match across both arrays, return true, indicating that through a series of reversals, arr can be transformed to match target.

This approach works efficiently under the constraints provided, as it essentially deals with counting sort principle, which is linear in terms of time complexity, i.e., O(n). This is sufficient given the maximum constraint of n = 1000.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    bool arraysEqual(vector<int>& first, vector<int>& second) {
        unordered_map<int, int> frequency;
        for (int val : second) {
            frequency[val]++;
        }

        for (int val : first) {
            if (frequency.find(val) == frequency.end()) return false;

            frequency[val]--;
            if (frequency[val] == 0) {
                frequency.erase(val);
            }
        }
        return frequency.empty();
    }
};

This solution checks if two arrays can be made equal by reversing subarrays using C++. The function arraysEqual takes two vectors first and second as input and utilizes an unordered map frequency to track the occurrence of each element in the second array.

  • Initially, populate frequency with the count of each element from the second array.
  • Iterate through the first array and decrement the corresponding counts in frequency. If an element from first is not found in frequency, return false immediately.
  • Remove the entry from the map if the count drops to zero to ensure that elements are not over-represented.

If the map is empty at the end of the traversal of the first array, it verifies that both arrays can be made equal by reversing subarrays, returning true. If not, the function returns false, indicating the arrays cannot be made equivalent through the allowed operations. This approach efficiently handles the comparison using hashing, providing a clear method to assess array equivalence through subarray reversals.

java 
class Solution {

    public boolean arraysEqual(int[] targetArray, int[] sourceArray) {
        // Generate frequency mapping for sourceArray
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int number : sourceArray) {
            frequencyMap.put(number, frequencyMap.getOrDefault(number, 0) + 1);
        }

        for (int number : targetArray) {
            // Check existence of number in targetArray against frequencyMap
            if (!frequencyMap.containsKey(number)) return false;

            // Adjust frequency and clean up if zero
            frequencyMap.put(number, frequencyMap.get(number) - 1);
            if (frequencyMap.get(number) == 0) {
                frequencyMap.remove(number);
            }
        }
        return frequencyMap.isEmpty();
    }
}

This Java solution determines if you can make the 'targetArray' identical to the 'sourceArray' by performing reverse operations on any subarrays of 'sourceArray'. The approach is to use a frequency map to count the occurrences of each element in sourceArray. The algorithm proceeds as follows:

  1. Initialize a HashMap to store the frequency of each element in sourceArray.
  2. Iterate over targetArray to ensure each number exists in the frequency map with a sufficient count.
  3. For every element in targetArray, decrement its count in the frequency map. If the frequency of a number goes to zero, remove it from the map.
  4. Finally, check if the frequency map is empty, indicating that all elements in sourceArray and targetArray perfectly match up in terms of both element and frequency.

If the frequency map is empty at the end of this process, the solution returns true, indicating that targetArray can be made equal to sourceArray by reversing subarrays; otherwise, it returns false. This solution leverages the properties of a hash map to efficiently track and match frequencies of elements between two arrays.

python 
class Solution:
    def checkEquality(self, target: List[int], array: List[int]) -> bool:
        freq_count = {}
        for item in array:
            freq_count[item] = freq_count.get(item, 0) + 1
        
        for item in target:
            if item not in freq_count:
                return False

            freq_count[item] -= 1
            if freq_count[item] == 0:
                del freq_count[item]

        return len(freq_count) == 0

The provided code solves the problem of determining whether two arrays can be made equal by reversing subarrays. The function checkEquality in Python accepts two parameters, target and array. It employs a hashmap (freq_count) to keep a frequency count of elements in the array.

  • For each element in the array, increase its count in the freq_count.
  • Then, iterate through each element in the target.
    • If an element from target is not present in freq_count, return False.
    • Otherwise, decrement the count of the element. If the count drops to zero, remove the element from freq_count.

Ultimately, check if freq_count is empty. If it is, both arrays can be made equal, hence return True. If not, return False.

This solution relies on the properties of dictionary operations in Python, which are efficient for counting and decrements operations, leading to a straightforward and effective approach to solving the problem.

Comments

No comments yet.