algoadvance

Leetcode 1389. Create Target Array in the Given Order

Problem Statement

Given two arrays nums and index. Your task is to create a target array under the following rules:

  1. Initially, the target array is empty.
  2. Inserting the elements of nums into target at the positions specified by index. Specifically, target[index[i]] should be nums[i].

Return the target array.

Example

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]

Clarifying Questions

  1. What is the maximum length of nums and index arrays?
    • The arrays will have the same length, with a maximum length constraint of 100.
  2. Are the input arrays guaranteed to be valid (i.e., index will always contain valid positions for insertion)?
    • Yes.

Strategy

  1. Initialize an empty target array.
  2. Iterate through nums and index simultaneously.
  3. For each element in nums, insert it into the target array at the position provided by the corresponding element in index.
  4. Return the final target array.

In C++, we can use the insert method of the vector class to perform the insertion at specific index positions.

Code

#include <iostream>
#include <vector>

std::vector<int> createTargetArray(const std::vector<int>& nums, const std::vector<int>& index) {
    std::vector<int> target;
    
    for (size_t i = 0; i < nums.size(); ++i) {
        target.insert(target.begin() + index[i], nums[i]);
    }
    
    return target;
}

int main() {
    // Sample input
    std::vector<int> nums = {0, 1, 2, 3, 4};
    std::vector<int> index = {0, 1, 2, 2, 1};
    
    // Function call
    std::vector<int> target = createTargetArray(nums, index);
    
    // Output result
    for (int num : target) {
        std::cout << num << " ";
    }
    return 0;
}

Time Complexity

However, given the constraints (maximum length of 100), this quadratic time complexity is manageable for this problem size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI