Given two integer arrays of equal length target and arr.
In one step, you can select any non-empty sub-array 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.
Example 1:
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 sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [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:
Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.
Example 3:
Input: target = [1,12], arr = [12,1]
Output: true
Example 4:
Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr doesn't have value 9 and it can never be converted to target.
Example 5:
Input: target = [1,1,1,1,1], arr = [1,1,1,1,1]
Output: true
Constraints:
target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000
Solution:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class CanBeEqualSoln
{
public bool CanBeEqual(int[] target, int[] arr)
{
var map = new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++)
{
if (map.ContainsKey(arr[i]))
{
map[arr[i]]++;
}
else
{
map.Add(arr[i], 1);
}
}
for (int i = 0; i < target.Length; i++)
{
if (!map.ContainsKey(target[i]))
{
return false;
}
if (map[target[i]] == 1)
{
map.Remove(target[i]);
}
else
{
map[target[i]]--;
}
}
return true;
}
}
}
Time Complexity: O(n)
Space Complexity: O(n)
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class CanBeEqualSolnTests
{
[TestMethod]
public void CanBeEqualSoln_First()
{
var target = new int[] { 1, 2, 3, 4 };
var arr = new int[] { 2, 4, 1, 3 };
var output = true;
var res = new CanBeEqualSoln().CanBeEqual(target, arr);
Assert.AreEqual(res, output);
}
[TestMethod]
public void CanBeEqualSoln_Second()
{
var target = new int[] { 3, 7, 9 };
var arr = new int[] { 3, 7, 11 };
var output = false;
var res = new CanBeEqualSoln().CanBeEqual(target, arr);
Assert.AreEqual(res, output);
}
[TestMethod]
public void CanBeEqualSoln_Third()
{
var target = new int[] { 7 };
var arr = new int[] { 7 };
var output = true;
var res = new CanBeEqualSoln().CanBeEqual(target, arr);
Assert.AreEqual(res, output);
}
[TestMethod]
public void CanBeEqualSoln_Fourth()
{
var target = new int[] { 1, 12 };
var arr = new int[] { 12, 1 };
var output = true;
var res = new CanBeEqualSoln().CanBeEqual(target, arr);
Assert.AreEqual(res, output);
}
[TestMethod]
public void CanBeEqualSoln_Fifth()
{
var target = new int[] { 1, 1, 1, 1, 1 };
var arr = new int[] { 1, 1, 1, 1, 1 };
var output = true;
var res = new CanBeEqualSoln().CanBeEqual(target, arr);
Assert.AreEqual(res, output);
}
}
}
