Blogs Hub

Make Two Arrays Equal by Reversing Sub-arrays - Easy - LeetCode - MiniTV

Make Two Arrays Equal by Reversing Sub-arrays - Easy - LeetCode - मिनी टीवी

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);
        }
    }
}