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