Sponsored
Sponsored
This approach leverages the property that reversing subarrays can reorder elements but will not affect the element counts. Thus, if the sorted versions of the arrays are the same, then the arrays can be made equal.
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) for in-place sort.
1#include <vector>
2#include <algorithm>
3
4bool canBeEqual(std::vector<int>& target, std::vector<int>& arr) {
5 std::sort(target.begin(), target.end());
6 std::sort(arr.begin(), arr.end());
7 return target == arr;
8}This C++ solution utilizes the STL sorting function and equality operator to compare sorted arrays.
Instead of sorting, we can simply count the occurrences of each element in both arrays. If the frequency distributions are the same, the arrays can be made equal.
Time complexity: O(n) for a single pass through the arrays.
Space complexity: O(1) as the frequency array size is constant.
1
public class Solution {
public bool CanBeEqual(int[] target, int[] arr) {
int[] counts = new int[1001];
for (int i = 0; i < target.Length; ++i) {
counts[target[i]]++;
counts[arr[i]]--;
}
foreach (int count in counts) {
if (count != 0) return false;
}
return true;
}
}C# uses an integer array for counting frequencies of elements, keeping the solution efficient.