algoadvance

Leetcode 1389. Create Target Array in the Given Order

Problem Statement

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

• Initially, the target array is empty.
• From left to right, read each element from nums and its corresponding index from index.
• Insert the element from nums at the position given by index.

Return the target array.

It is guaranteed that the insertion positions will be valid.

Clarifying Questions

1. Input Constraints:
   • nums.length == index.length
   • Both nums and index are non-empty arrays.
   • The arrays could have up to 100 elements (1 <= nums.length, index.length <= 100).
2. Output:
   • Return an array that is formed by inserting the elements of nums at positions defined by index.

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]

Strategy

1. Initialize an empty list target.
2. Iterate through pairs of elements from nums and index.
3. For each pair, insert the element from nums at the specified position from index into the target list.
4. Convert the list target to an array and return it.

Time Complexity

• Insertion Operation Complexity: Each insertion operation in a list in Java can take up to O(n) time in the worst case, where n is the number of elements in the list at the time of insertion.
• Total Time Complexity: For n insertions, the time complexity will be O(n^2).

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> target = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            target.add(index[i], nums[i]);
        }

        // Convert the target list to array
        int[] result = new int[target.size()];
        for (int i = 0; i < target.size(); i++) {
            result[i] = target.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {0, 1, 2, 3, 4};
        int[] index = {0, 1, 2, 2, 1};

        int[] result = sol.createTargetArray(nums, index);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

This code snippet defines a Solution class with a method createTargetArray taking two integer arrays nums and index, and produces the desired target array following the insertion rules specified in the problem. The main method also includes an example to demonstrate the usage of the function.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?