Create Target Array in the Given Order — Problem & Solution
Create Target Array in the Given Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Create Target Array in the Given Order is an easy coding problem on arrays and simulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays of equal length, nums and index. Build a target array by repeating, for i from 0 upward, the step: insert nums[i] at position index[i] in the target array.
Inserting shifts everything from that position onward one place to the right. Return the finished target array.
Example 1
Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [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]
Example 3
Input: nums = [1], index = [0]
Output: [1]
Constraints
1 <= nums.length <= 40nums.length == index.length0 <= index[i] <= i0 <= nums[i] <= 100
Hints for Create Target Array in the Given Order
Hint 1
The constraint
index[i] <= iguarantees the position always exists when you get there.Hint 2
Simulate literally — an insert into a dynamic list is exactly the operation described.
How to solve Create Target Array in the Given Order
Simulate literally: insert nums[i] at position index[i] in a growing list.
Approach
- Start with an empty list.
- For each
(value, pos)pair in order, insertvalueatpos, shifting later elements right.
Why it works
The guarantee index[i] <= i means the position always exists at the moment of insertion, so the simulation never goes out of range.
Complexity
- Time —
O(n²) worst case for the shifts - Space —
O(n)
Pitfalls
- Assignment (
target[pos] = value) instead of insertion overwrites rather than shifts.
Reference solution
Python
def createTargetArray(nums, index):
out = []
for value, pos in zip(nums, index):
out.insert(pos, value)
return outJava
public static int[] createTargetArray(int[] nums, int[] index) {
List<Integer> out = new ArrayList<>();
for (int i = 0; i < nums.length; i++) out.add(index[i], nums[i]);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
vector<int> out;
for (size_t i = 0; i < nums.size(); i++) {
out.insert(out.begin() + index[i], nums[i]);
}
return out;
}JavaScript
var createTargetArray = function(nums, index) {
const out = [];
for (let i = 0; i < nums.length; i++) {
out.splice(index[i], 0, nums[i]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays