algoadvance

Leetcode 1460. Make Two Arrays Equal by Reversing Subarrays

Problem Statement

Given two integer arrays target and arr, you can perform the following operation on arr any number of times:

Return True if you can make arr equal to target, or False otherwise.

Clarifying Questions

  1. Are the elements in the arrays always integers?
    • Yes.
  2. Can the arrays contain duplicate elements?
    • Yes.
  3. Are the lengths of target and arr always the same?
    • Yes.
  4. What are the constraints on the size of the arrays?
    • The length of target and arr will be in the range [1, 1000].

Strategy

Reversing subarrays implies that we can rearrange the elements in arr in any order. Therefore, the problem reduces to checking if both arrays contain the same elements with the same frequencies.

The easiest way to do this is to:

  1. Sort both arrays.
  2. Compare them element by element.

If the sorted arrays are identical, then arr can be transformed into target by a series of subarray reversals. If not, it cannot.

Time Complexity

So, the overall time complexity is (O(n \log n)), which is efficient for the given constraints.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    bool canBeEqual(std::vector<int>& target, std::vector<int>& arr) {
        // Sort both target and arr
        std::sort(target.begin(), target.end());
        std::sort(arr.begin(), arr.end());
        
        // Compare the sorted arrays
        return target == arr;
    }
};

Explanation

  1. Sorting: We sort both target and arr.
  2. Comparison: We use the == operator to check if the sorted arrays are identical.

This method ensures that we are checking if both arrays can be rearranged to be the same, which is the core requirement of the problem.

Conclusion

This solution is efficient and leverages sorting to simplify the problem of checking for equality after potentially unlimited subarray reversals.

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