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.

Examples

Example 1:

1
2
3
4
5
6
7

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

1
2
3

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

1
2
3

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

Solution

Method 1 - Using Frequency map

A key insight here is that since reversing subarrays can be done any number of times, the relative ordering of elements within arr can be entirely changed. Therefore, transforming arr into target is possible if and only if both arrays contain the exact same elements in the same frequencies.

Steps

  1. Count Element Frequencies:
    • Count the frequency of each element in both target and arr.
  2. Compare Counts:
    • If the frequency of each element in both arrays is the same, then it is possible to transform arr into target through reversing operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {

	public boolean canBeEqual(int[] target, int[] arr) {
		if (target.length != arr.length) {
			return false;
		}

		Map<Integer, Integer> targetCount = new HashMap<>();
		Map<Integer, Integer> arrCount = new HashMap<>();

		for (int i = 0; i < target.length; i++) {
			// Count elements in `target`
			targetCount.put(target[i], targetCount.getOrDefault(target[i], 0) + 1);
			// Count elements in `arr`
			arrCount.put(arr[i], arrCount.getOrDefault(arr[i], 0) + 1);
		}

		// Compare the two maps
		return targetCount.equals(arrCount);
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is number of elements in target or arr arrays.
  • 🧺 Space complexity: O(n) for storing values in frequency map