Create Target Array in the Given Order

Create Target Array in the Given Order

What is this problem about?

The Create Target Array in the Given Order interview question asks you to construct a result array based on two input arrays: nums and index. For each pair (nums[i], index[i]), you must insert the value nums[i] at the position index[i] in the target array. Any existing elements at or to the right of that index must be shifted one position to the right.

Why is this asked in interviews?

Companies like Uber and Adobe use this simulation interview pattern to test basic array manipulation skills. While the logic is simple, it evaluates a candidate's understanding of array insertion costs. In many languages, inserting into the middle of an array is an O(N) operation, making the overall complexity O(N^2). It's a fundamental test of "Simulation" and handling dynamic lists.

Algorithmic pattern used

This is a Simulation problem.

1. Initialize an empty list or dynamic array.
2. Iterate through nums and index simultaneously.
3. Use the built-in insert(pos, val) method of your language's dynamic array (like ArrayList in Java or list in Python).
4. If the language doesn't have an insert method, you must manually shift elements to the right before placing the new value.

Example explanation

nums = [0, 1, 2], index = [0, 1, 1]

1. Insert 0 at index 0: [0].
2. Insert 1 at index 1: [0, 1].
3. Insert 2 at index 1:
   • Shift 1 to the right.
   • Place 2 at index 1.
   • Result: [0, 2, 1].

Common mistakes candidates make

• Overwriting vs. Inserting: Accidental assignment (target[index[i]] = nums[i]) instead of shifting and inserting.
• Fixed-size Arrays: Not accounting for the growing size of the target array if using a static array structure.
• Complexity Discussion: Not being able to explain why the complexity is O(N^2) even when using a built-in insert function.

Interview preparation tip

Always be ready to discuss the time complexity of "built-in" functions. Just because you write one line of code (list.insert) doesn't mean it's an O(1) operation.