We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Create Target Array in the Given Order

Number: 1505

Difficulty: Easy

Paid? No

Companies: Google, Visa, Amazon

Problem Description

Given two arrays of integers, nums and index, construct the target array by inserting elements from nums into target at the positions specified by index. Start with an empty target array and insert each nums[i] at position index[i]. Return the target array after all insertions.

Key Insights

  • Simulate the insertion process as described in the problem.
  • Each insertion may cause elements to shift to the right.
  • Since index[i] is always between 0 and i, the insertion is always valid.
  • The problem can be solved efficiently with dynamic array/list data structures.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario due to shifting elements during insertion, where n is the length of the array. Space Complexity: O(n) for storing the target array.

Solution

We iterate through both nums and index simultaneously. For each element:

  1. Insert the element from nums at the position specified by the corresponding element in index.
  2. Use the dynamic array/list insertion capabilities of high-level languages (like Python's list.insert or JavaScript's Array.splice). The algorithm efficiently constructs the target array using the insertion operations provided by the language. Although each insertion may take O(n) time due to element shifting, the constraint of up to 100 elements keeps the overall performance acceptable.

Code Solutions

# Python solution with detailed comments
def createTargetArray(nums, index):
    # Initialize an empty list for the target array.
    target = []
    # Iterate through each number and its corresponding index.
    for num, idx in zip(nums, index):
        # Insert num at the given idx in the target list.
        target.insert(idx, num)
    # Return the resulting target array.
    return target

# Example usage:
nums = [0, 1, 2, 3, 4]
index = [0, 1, 2, 2, 1]
print(createTargetArray(nums, index))  # Output: [0, 4, 1, 3, 2]
← Back to All Questions