algoadvance

Leetcode 1460. Make Two Arrays Equal by Reversing Subarrays

Problem Statement

You are given two integer arrays target and arr of the same length. In one operation, you can select any non-empty subarray of arr and reverse it. 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 reverse subarrays [2], [4,1], and [3] to make arr equal to target.

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 the value 9 and it cannot be made equal to target.

Clarifying Questions

1. Constraints:
   • Both arrays have the same length.
   • The elements of the arrays are integers.
   • Could the arrays contain duplicate elements? (Yes, typical array problems allow this.)
   • Do the values within the arrays fall within a certain range? (Not specified, so assume general integer range.)
2. Edge Cases:
   • Arrays with a single element.
   • Arrays with all elements being the same.
   • Arrays where elements are already in the correct order.

Strategy

To determine if the two arrays can be made equal by reversing subarrays, we need to note the following:

1. If both arrays have the same elements with the same frequencies, then it’s possible to transform arr to target by some series of subarray reversals. This is because reversals do not change the frequency of elements in the array.

2. Therefore, the problem reduces to checking if both arrays are permutations of each other.

Code

Here’s the Java code to solve the problem:

import java.util.HashMap;

public class MakeTwoArraysEqual {
    public static boolean canBeEqual(int[] target, int[] arr) {
        HashMap<Integer, Integer> targetMap = new HashMap<>();
        HashMap<Integer, Integer> arrMap = new HashMap<>();
        
        // Fill the frequency maps
        for (int num : target) {
            targetMap.put(num, targetMap.getOrDefault(num, 0) + 1);
        }
        
        for (int num : arr) {
            arrMap.put(num, arrMap.getOrDefault(num, 0) + 1);
        }

        // Compare the maps
        return targetMap.equals(arrMap);
    }
    
    public static void main(String[] args) {
        int[] target1 = {1, 2, 3, 4};
        int[] arr1 = {2, 4, 1, 3};
        System.out.println(canBeEqual(target1, arr1)); // Output: true
        
        int[] target2 = {7};
        int[] arr2 = {7};
        System.out.println(canBeEqual(target2, arr2)); // Output: true
        
        int[] target3 = {3, 7, 9};
        int[] arr3 = {3, 7, 11};
        System.out.println(canBeEqual(target3, arr3)); // Output: false
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the arrays. This is because we are simply iterating over the arrays to build the frequency maps and then comparing the maps, which takes linear time.
• Space Complexity: O(n), as we are using frequency maps to store the counts of the elements in both arrays.

This is an efficient and straightforward approach to solving the problem by leveraging the properties of permutations and hashing for frequency counting.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?