Make Two Arrays Equal by Reversing Subarrays

Make Two Arrays Equal by Reversing Subarrays - Problem

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can make arr equal to target or false otherwise.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: target = [1,2,3,4], arr = [2,4,1,3]

› Output: true

💡 Note: Both arrays contain the same elements [1,2,3,4]. We can reverse subarrays to rearrange arr into target: reverse [2,4] to get [4,2,1,3], then reverse [4,2,1] to get [1,2,4,3], then reverse [4,3] to get [1,2,3,4].

Example 2 — Different Elements

$ Input: target = [7], arr = [1]

› Output: false

💡 Note: The arrays contain different elements. arr has [1] while target has [7]. No amount of reversing can change the element values, only their positions.

Example 3 — Duplicate Elements

$ Input: target = [1,1,1,1,1], arr = [1,1,1,1,1]

› Output: true

💡 Note: Both arrays contain the same elements with the same frequencies (five 1's). Since they're identical, they're already equal.

Constraints

target.length == arr.length
1 ≤ target.length ≤ 1000
1 ≤ target[i] ≤ 1000
1 ≤ arr[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: target=[1,2,3,4] and arr=[2,4,1,3]

Process

Check if arrays contain same elements (reversals only change order, not values)

Output

Return true if same elements, false otherwise

Key Takeaway

🎯 Key Insight: Subarray reversals can rearrange elements into any order, so arrays are equal if they contain the same elements

Asked in

G Google 15 A Amazon 12 M Microsoft 8 F Facebook 6

The key insight is that if we can reverse any subarray any number of times, we can rearrange elements into any order. Two arrays can be made equal if and only if they contain the same elements with the same frequencies. Best approach is sorting both arrays and comparing them. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Compare	O(n log n)	O(1)	Sort both arrays and check if they are identical
Brute Force - Try All Reversals	O(2^n)	O(n)	Systematically try all possible subarray reversals until target is matched
Frequency Count Comparison	O(n)	O(n)	Count frequency of each element in both arrays and compare

Sort and Compare — Algorithm Steps

Sort the target array
Sort the arr array
Compare sorted arrays element by element

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Arrays

Start with target and arr arrays

Sort Both

Sort both arrays in ascending order

Compare

If sorted arrays are identical, original arrays can be made equal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool solution(int* target, int* arr, int n) {
    // Create copies to avoid modifying original arrays
    int* targetCopy = malloc(n * sizeof(int));
    int* arrCopy = malloc(n * sizeof(int));
    
    memcpy(targetCopy, target, n * sizeof(int));
    memcpy(arrCopy, arr, n * sizeof(int));
    
    // Sort both arrays
    qsort(targetCopy, n, sizeof(int), compare);
    qsort(arrCopy, n, sizeof(int), compare);
    
    // Compare sorted arrays
    bool result = true;
    for (int i = 0; i < n; i++) {
        if (targetCopy[i] != arrCopy[i]) {
            result = false;
            break;
        }
    }
    
    free(targetCopy);
    free(arrCopy);
    return result;
}

int main() {
    // Simplified parsing for C
    int target[] = {1, 2, 3, 4};
    int arr[] = {2, 4, 1, 3};
    int n = 4;
    
    bool result = solution(target, arr, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting both arrays takes O(n log n) time

⚡ Linearithmic

Space Complexity

O(1)

Sorting is done in-place, no extra space needed

✓ Linear Space

32.0K Views

Medium Frequency

~8 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Compare — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler