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 <stdbool.h>
2#include <stdlib.h>
3
4int cmpFunc(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8bool canBeEqual(int *target, int targetSize, int *arr, int arrSize) {
9 qsort(target, targetSize, sizeof(int), cmpFunc);
10 qsort(arr, arrSize, sizeof(int), cmpFunc);
11 for (int i = 0; i < targetSize; ++i) {
12 if (target[i] != arr[i]) {
13 return false;
14 }
15 }
16 return true;
17}This solution sorts both arrays and then compares them element by element.
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.
1Java's solution also uses an integer array to maintain frequency counts to compare both arrays.