Blogs Hub

Create Target Array in the Given Order - Array - Easy - LeetCode - MiniTV

Create Target Array in the Given Order - Array - Easy - LeetCode - मिनी टीवी

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

Initially, target array is empty.

From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.

Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

 

Example 1:

 

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]

Output: [0,4,1,3,2]

Explanation:

nums       index     target

0            0        [0]

1            1        [0,1]

2            2        [0,1,2]

3            2        [0,1,3,2]

4            1        [0,4,1,3,2]

 

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]

Output: [0,1,2,3,4]

Explanation:

nums       index     target

1            0        [1]

2            1        [1,2]

3            2        [1,2,3]

4            3        [1,2,3,4]

0            0        [0,1,2,3,4]

 

Example 3:

Input: nums = [1], index = [0]

Output: [1]

 

Constraints:

1 <= nums.length, index.length <= 100

nums.length == index.length

0 <= nums[i] <= 100

0 <= index[i] <= i

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class CreateTargetArraySoln
    {
        public int[] CreateTargetArray(int[] nums, int[] index)
        {
            var target = new int[nums.Length];
            var set = new HashSet<int>();
            for(int i = 0; i < nums.Length; i++)
            {
                if (set.Contains(index[i]))
                {
                    for (int j = nums.Length-1; j > index[i]; j--)
                    {
                        target[j] = target[j - 1];
                        set.Add(j);
                    }
                }  
                
                target[index[i]] = nums[i];
                set.Add(index[i]);                
            }

            return target;
        }
    }
}

 

Time Complexity: O(n^2)

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 CreateTargetArraySolnTests
    {
        [TestMethod]
        public void CreateTargetArraySoln_First()
        {
            var nums = new int[] { 0, 1, 2, 3, 4 };
            var index = new int[] { 0, 1, 2, 2, 1 };
            var output = new int[] { 0, 4, 1, 3, 2 };
            var res = new CreateTargetArraySoln().CreateTargetArray(nums, index);

            AreEqual(res, output);
        }
        
        [TestMethod]
        public void CreateTargetArraySoln_Second()
        {
            var nums = new int[] { 1, 2, 3, 4, 0 };
            var index = new int[] { 0, 1, 2, 3, 0 };
            var output = new int[] { 0, 1, 2, 3, 4 };
            var res = new CreateTargetArraySoln().CreateTargetArray(nums, index);

            AreEqual(res, output);
        }

        [TestMethod]
        public void CreateTargetArraySoln_Third()
        {
            var nums = new int[] { 1 };
            var index = new int[] { 0 };
            var output = new int[] { 1 };
            var res = new CreateTargetArraySoln().CreateTargetArray(nums, index);

            AreEqual(res, output);
        }

        [TestMethod]
        public void CreateTargetArraySoln_Fourth()
        {

            var nums = new int[] { 4, 2, 4, 3, 2 };
            var index = new int[] { 0, 0, 1, 3, 1 };
            var output = new int[] { 2, 2, 4, 4, 3 };
            var res = new CreateTargetArraySoln().CreateTargetArray(nums, index);

            AreEqual(res, output);
        }

        private void AreEqual(int[] res, int[] output)
        {
            Assert.AreEqual(res.Length, output.Length);

            for (int i = 0; i < res.Length; i++)
            {
                Assert.AreEqual(res[i], output[i]);
            }
        }
    }
}