Create Target Array in the Given Order

Difficulty: Easy | Acceptance: 86.50% | Paid: No Topics: Array, Simulation

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] in target array the value nums[i]. 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.

• Examples
• Constraints
• Simulation (Built-in Insert)
• Simulation (Manual Shifting)
• [Binary Indexed Tree]((#binary-indexed-tree)

Examples

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

Simulation (Built-in Insert)

Intuition Most programming languages provide a built-in data structure (like a List or ArrayList) that supports dynamic insertion at arbitrary indices. We can iterate through the input arrays and use this built-in functionality to construct the target array directly.

Steps

• Initialize an empty list called target.
• Iterate i from 0 to nums.length - 1.
• At each step, insert nums[i] into target at position index[i].
• Return target.

class Solution:
    def createTargetArray(self, nums: list[int], index: list[int]) -> list[int]:
        target = []
        for i in range(len(nums)):
            target.insert(index[i], nums[i])
        return target

Complexity

• Time: O(n²) - Inserting an element at the beginning of a dynamic array requires shifting all existing elements, which takes O(n) time. Doing this n times results in O(n²).
• Space: O(n) - To store the result.
• Notes: Simple and readable, but not the most efficient for large arrays due to shifting overhead.

Simulation (Manual Shifting)

Intuition To avoid the overhead of dynamic array resizing or built-in method abstractions, we can simulate the insertion process manually. Since we know the maximum size of the array beforehand, we can allocate a fixed-size array and shift elements to the right to make space for the new element at the specified index.

Steps

• Initialize an array target of size n (where n is the length of nums).
• Iterate i from 0 to n - 1.
• For each i, shift elements in target from index i - 1 down to index[i] one position to the right.
• Place nums[i] at target[index[i]].
• Return target.

class Solution:
    def createTargetArray(self, nums: list[int], index: list[int]) -> list[int]:
        n = len(nums)
        target = [0] * n
        for i in range(n):
            idx = index[i]
            # Shift elements to the right
            for j in range(i, idx, -1):
                target[j] = target[j - 1]
            target[idx] = nums[i]
        return target

Complexity

• Time: O(n²) - The nested loop for shifting elements results in a quadratic time complexity.
• Space: O(n) - To store the result.
• Notes: This approach mimics the low-level behavior of array insertion.

Binary Indexed Tree

Intuition For a more advanced solution, we can use a Binary Indexed Tree (Fenwick Tree) to efficiently find the k-th empty slot in the array. This approach treats the array indices as positions in a sequence where we need to find the index[i]-th available spot (0-indexed). This is particularly useful if the constraints were much larger (e.g., n = 10⁵), where O(n²) would be too slow.

Steps

• Initialize a Binary Indexed Tree of size n with all values set to 1 (representing n empty slots).
• Iterate through nums and index.
• For each index[i], we need to find the position of the (index[i] + 1)-th ‘1’ in the BIT (the k-th empty slot). This can be done using binary lifting on the BIT.
• Once the position pos is found, place nums[i] at pos - 1 in the result array.
• Update the BIT at pos by subtracting 1 (marking the slot as filled).
• Return the result array.

class Solution:
    def createTargetArray(self, nums: list[int], index: list[int]) -> list[int]:
        n = len(nums)
        bit = [0] * (n + 2)
        
        def update(i, delta):
            while i <= n:
                bit[i] += delta
                i += i & -i
        
        def query(i):
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & -i
            return s
        
        def find_kth(k):
            idx = 0
            bit_mask = 1 << (n.bit_length())
            while bit_mask:
                t_idx = idx + bit_mask
                if t_idx <= n and bit[t_idx] < k:
                    idx = t_idx
                    k -= bit[t_idx]
                bit_mask >>= 1
            return idx + 1

        for i in range(1, n + 1):
            update(i, 1)

        res = [0] * n
        for i in range(n):
            k = index[i] + 1
            pos = find_kth(k)
            res[pos - 1] = nums[i]
            update(pos, -1)
        return res

Complexity

• Time: O(n log n) - Each update and query operation on the BIT takes O(log n) time.
• Space: O(n) - To store the BIT and the result array.
• Notes: This is the most efficient approach for large input sizes, though it is overkill for the given constraints (n <= 100).