LeetCode 1460 - Make Two Arrays Equal by Reversing Subarrays

LeetCode Problem 1460

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

This problem asks whether one integer array, arr, can be transformed into another array, target, by repeatedly reversing any non-empty contiguous subarray.

A subarray reversal means choosing a continuous segment of the array and reversing the order of its elements. For example, reversing [2,4,1] changes it into [1,4,2].

The key detail is that you may perform any number of reversals, and the chosen subarray can be of any non-zero length. Because there is no restriction on how many operations you can perform, the question is not about finding the sequence of operations. Instead, it is asking whether such a transformation is theoretically possible.

The input consists of two arrays:

• target, the desired final arrangement
• arr, the starting arrangement

Both arrays have the same length.

The output is a boolean:

• Return true if arr can be rearranged into target
• Return false otherwise

The constraints tell us several important things:

• The array length is at most 1000, which is relatively small
• Element values range from 1 to 1000
• Both arrays always have equal length

Since values may repeat, we must account for frequency, not just presence. For example, [1,2,2] and [1,1,2] contain similar values but are not transformable into each other because the counts differ.

The most important observation is understanding what repeated subarray reversals allow us to do. Since reversing a subarray of length 2 effectively swaps adjacent elements, and adjacent swaps can generate any permutation of an array, the exact order of elements is not important. What matters is whether both arrays contain the same multiset of elements, meaning the same numbers with the same frequencies.

Some edge cases that could trip up a naive implementation include arrays of length 1, repeated values, or arrays that contain the same numbers but in very different orders. Fortunately, the problem guarantees equal lengths, so we never need to handle mismatched sizes.

Approaches

Brute Force Approach

A brute force solution would attempt to simulate all possible sequences of subarray reversals to see whether arr can eventually become target.

At each step, we could generate every possible subarray reversal and recursively or iteratively explore all resulting states. Since there are O(n²) possible subarrays for each operation, and transformations can continue indefinitely, the number of reachable states grows explosively.

This approach is theoretically correct because it eventually explores every possible arrangement reachable through reversals. If target is reachable, brute force will eventually find it.

However, this method is far too slow. The number of permutations of an array is n!, and exploring transformations between them becomes computationally infeasible even for moderate input sizes. With n = 1000, such an approach is completely impractical.

Optimal Approach, Compare Element Frequencies

The key insight is recognizing what repeated subarray reversals allow.

Reversing a subarray of length 2 swaps adjacent elements. Since any permutation can be achieved through a sequence of adjacent swaps, we can rearrange arr into any ordering of its elements.

This means the only thing that matters is whether both arrays contain the exact same elements with the same counts.

There are two common ways to verify this:

1. Sort both arrays and compare them.
2. Count frequencies using a hash map.

A frequency map is more direct and avoids sorting. We count how many times each value appears in target, then subtract counts while traversing arr. If all counts balance perfectly, transformation is possible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Explores possible reversal sequences, computationally infeasible
Optimal	O(n)	O(n)	Uses a hash map to compare element frequencies

Algorithm Walkthrough

We will use a hash map to count element frequencies.

1. Create a frequency map for target.

We first count how many times each number appears in target. The key is the number, and the value is its frequency.

For example:

target = [1,2,3,4]

Produces:

{
    1: 1,
    2: 1,
    3: 1,
    4: 1
}

This map represents the exact elements required to build target. 2. Traverse arr and reduce counts.

For every number in arr, decrease its count in the map.

If a number does not exist in the map or its count becomes negative, then arr contains too many of that value, which means transformation is impossible. 3. Verify all counts are zero.

After processing every element in arr, every required count should be exactly zero.

If any value still has a non-zero count, then arr is missing some required element. 4. Return the result.

If all frequencies match perfectly, return True. Otherwise, return False.

Why it works

The correctness relies on an important property: any permutation of an array can be generated using adjacent swaps, and an adjacent swap is simply a reversal of a subarray of length 2.

Since arbitrary reordering is possible, the only invariant that remains unchanged during reversals is the multiset of elements. Reversals never create or destroy values, they only rearrange them. Therefore, arr can become target if and only if both arrays contain exactly the same values with the same frequencies.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        frequency = defaultdict(int)

        # Count elements in target
        for num in target:
            frequency[num] += 1

        # Remove counts using arr
        for num in arr:
            if frequency[num] == 0:
                return False
            frequency[num] -= 1

        return True

The implementation follows the algorithm directly.

We first create a hash map called frequency using defaultdict(int), which automatically initializes missing keys to 0. This simplifies frequency tracking because we do not need to manually check whether a key exists.

Next, we iterate through target and count how many times each number appears. This establishes the expected element distribution.

We then process arr. For each number, we check whether that value is still available in the frequency map. If its count is already 0, it means arr contains an extra occurrence of that number or an invalid value, so we immediately return False.

Otherwise, we decrement the count to indicate that one required occurrence has been matched.

If we finish processing without any mismatch, the arrays contain identical multisets of elements, so the transformation is always possible, and we return True.

Go Solution

func canBeEqual(target []int, arr []int) bool {
	frequency := make(map[int]int)

	// Count elements in target
	for _, num := range target {
		frequency[num]++
	}

	// Remove counts using arr
	for _, num := range arr {
		if frequency[num] == 0 {
			return false
		}
		frequency[num]--
	}

	return true
}

The Go implementation mirrors the Python logic closely.

A map[int]int is used to store frequencies. Missing keys automatically return 0, which simplifies existence checks.

While traversing arr, we immediately return false if a value has no remaining count available. Otherwise, we decrement the frequency.

There are no concerns about integer overflow because values and counts are small. Since slices in Go are dynamically sized references, we process them directly without needing explicit array handling. Empty versus nil slices are irrelevant here because the problem guarantees valid input arrays with equal lengths.

Worked Examples

Example 1

target = [1,2,3,4]
arr = [2,4,1,3]

Step 1: Build frequency map

Element	Frequency Map
1	{1:1}
2	{1:1, 2:1}
3	{1:1, 2:1, 3:1}
4	{1:1, 2:1, 3:1, 4:1}

Step 2: Process arr

Current Value	Action	Updated Map
2	decrement	{1:1, 2:0, 3:1, 4:1}
4	decrement	{1:1, 2:0, 3:1, 4:0}
1	decrement	{1:0, 2:0, 3:1, 4:0}
3	decrement	{1:0, 2:0, 3:0, 4:0}

All counts match.

Result: True

Example 2

target = [7]
arr = [7]

Step 1: Build frequency map

{7: 1}

Step 2: Process arr

Current Value	Action	Updated Map
7	decrement	{7:0}

All counts become zero.

Result: True

Example 3

target = [3,7,9]
arr = [3,7,11]

Step 1: Build frequency map

{
    3: 1,
    7: 1,
    9: 1
}

Step 2: Process arr

Current Value	Action	Updated Map
3	decrement	{3:0, 7:1, 9:1}
7	decrement	{3:0, 7:0, 9:1}
11	invalid, count is 0	return False

The number 11 does not exist in target.

Result: False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count target, one pass to process arr
Space	O(n)	Hash map stores frequencies of distinct elements

The algorithm performs two linear passes over arrays of length n. Hash map operations are O(1) on average, so the total running time is linear.

The extra space depends on how many unique values appear. In the worst case, every element is distinct, requiring O(n) additional storage.

Test Cases

solution = Solution()

# Provided examples
assert solution.canBeEqual([1, 2, 3, 4], [2, 4, 1, 3]) is True  # reorder possible
assert solution.canBeEqual([7], [7]) is True  # already equal
assert solution.canBeEqual([3, 7, 9], [3, 7, 11]) is False  # missing element

# Boundary cases
assert solution.canBeEqual([1], [1]) is True  # minimum size, same value
assert solution.canBeEqual([1], [2]) is False  # minimum size, different value

# Repeated values
assert solution.canBeEqual([1, 2, 2, 3], [2, 3, 2, 1]) is True  # same frequencies
assert solution.canBeEqual([1, 2, 2], [1, 1, 2]) is False  # different frequencies

# Already equal
assert solution.canBeEqual([5, 6, 7], [5, 6, 7]) is True  # no operations needed

# Reverse order
assert solution.canBeEqual([1, 2, 3, 4], [4, 3, 2, 1]) is True  # full reversal works

# Missing value
assert solution.canBeEqual([1, 2, 3], [1, 2, 4]) is False  # one value differs

# Large repeated values
assert solution.canBeEqual([1000] * 1000, [1000] * 1000) is True  # maximum identical case

Test Case Summary

Test	Why
[1,2,3,4] vs [2,4,1,3]	Valid rearrangement through reversals
[7] vs [7]	Smallest valid input
[3,7,9] vs [3,7,11]	Missing required element
[1] vs [2]	Single element mismatch
Duplicate values	Verifies frequency counting
Already equal arrays	Ensures no operations are required
Reverse order arrays	Confirms arbitrary permutations are possible
Different frequencies	Detects repeated-value mismatches
Maximum repeated input	Stress test for constraints

Edge Cases

Arrays of Length One

The smallest possible input size is 1. In this case, no meaningful rearrangement is possible because there is only one element. The result depends entirely on whether the values match.

A buggy implementation might overcomplicate this case or attempt invalid operations. Our frequency-based solution handles it naturally because matching counts immediately succeed or fail.

Duplicate Values

Repeated elements are a common source of mistakes. For example:

target = [1,2,2]
arr = [1,1,2]

A naive solution that only checks whether elements exist would incorrectly return True. The problem requires matching frequencies, not just presence.

Our hash map tracks exact counts, ensuring duplicates are handled correctly.

Same Elements in Different Orders

Arrays may contain identical values but appear completely shuffled:

target = [1,2,3,4]
arr = [4,1,3,2]

A naive comparison using direct equality would fail because the order differs.

Our implementation correctly recognizes that unlimited subarray reversals allow arbitrary reordering, so only the multiset of values matters.

Missing or Extra Elements

If arr contains a number not present in target, transformation is impossible.

For example:

target = [1,2,3]
arr = [1,2,99]

When processing 99, the frequency count is already 0, causing an immediate False return. This early exit avoids unnecessary computation and guarantees correctness.