Jobs

Interviews

Discussions

Create Target Array in the Given Order

Easy

Visa

2 views

Topics:

Arrays

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

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

Create Target Array in the Given Order

Easy

Visa

2 views

Topics:

Arrays

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

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for elements in the `nums` array and `index` array?
Can the `index` values be out of bounds for the target array at any point during the insertion process, or are they guaranteed to be valid?
If the `index` array contains duplicate indices, how should I handle those when inserting elements?
Are the lengths of the `nums` and `index` arrays guaranteed to be the same, and are they guaranteed to be non-empty?
What should I return if the input arrays are invalid, such as being null or having different lengths?

Brute Force Solution

Approach

We're building a new list by inserting numbers from an existing list into specific spots. A simple, but potentially slow, way to do this is to insert each number one at a time, shifting the other numbers as needed to make space.

Here's how the algorithm would work step-by-step:

Take the first number from the first list.
Look at the corresponding position in the second list. This position tells you where to put the number in your new list.
Put the first number into the indicated position in the new list. If there was already a number in that position, shift it and all the following numbers to the right to make space.
Repeat this process for each subsequent number in the first list.
For each number in the first list, use the corresponding position in the second list to figure out where to put the new number in the new list.
Keep shifting numbers to the right as needed to insert the new number into the correct spot.
After processing all the numbers in the first list, the new list should be complete and have all the numbers in the requested order.

Code Implementation

def create_target_array(numbers, indices):    target_array = []
    for i in range(len(numbers)):        index_to_insert_at = indices[i]
        # Insert the number at the specified index.
        # This might require shifting existing elements.
        target_array = target_array[:index_to_insert_at] + [numbers[i]] + target_array[index_to_insert_at:]

    return target_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element, it inserts the element at a specified index in the target array. Inserting an element into an array at a specific index requires shifting the existing elements to the right, which can take up to n operations in the worst case (inserting at the beginning). Therefore, the overall time complexity is n (iterations) * n (shifting) which equals to n². This results in a time complexity of O(n²).

Space Complexity

O(N) – The described solution involves inserting elements into a new list, shifting existing elements to the right. The new list, which holds the created target array, grows with each insertion. In the worst case, all elements from the input array 'nums' are inserted, leading to a target array of size N, where N is the length of the input array 'nums'. Therefore, the auxiliary space required to store this target array is proportional to N, resulting in a space complexity of O(N).

Optimal Solution

Approach

We need to construct a new array following a specific order defined by two input arrays. The key idea is to directly insert elements into the correct positions of a new array as we iterate. To do this efficiently, we'll leverage the ability to insert at a specific location within a data structure that allows dynamic resizing and shifting of elements.

Here's how the algorithm would work step-by-step:

Begin with an empty list-like structure that can grow as needed.
Take the first number from the numbers array and the corresponding position from the positions array.
Insert the number into the list at the indicated position.
Repeat the process for each number and position in the input arrays, inserting each number into the list at the specified position.
The list will automatically manage shifting existing elements to make space for the new insertions, maintaining the correct order.
Once you've processed all the numbers and positions, convert the list into the final array.
The resulting array will be in the target order, constructed by directly inserting elements into their correct spots.

Code Implementation

def create_target_array(numbers, positions):
    target_array = []

    # Iterate through the input arrays
    for index in range(len(numbers)):
        # Insert the number at the specified position
        target_array.insert(positions[index], numbers[index])

    return target_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input arrays of size n. For each element, it inserts into a list at a specific index. The insertion operation on a list or array requires shifting existing elements to accommodate the new element, and in the worst case, this could involve shifting close to n elements. Therefore, inserting one element takes O(n) time, and since this is done for each of the n elements, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm uses a list-like structure to store the elements as they are inserted at specific positions. This list grows dynamically to accommodate the inserted numbers. In the worst case, the list will contain all N numbers from the input array. Therefore, the auxiliary space used is proportional to the number of elements in the input array (N), resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty nums and index arrays	Return an empty array or throw an IllegalArgumentException if either input is null or empty.
nums and index arrays of different lengths	Throw an IllegalArgumentException because the index array needs a corresponding value from the nums array to be inserted.
index array contains negative indices	Throw an IllegalArgumentException since indices must be non-negative.
index array contains indices out of bounds (>= nums.length)	Throw an IndexOutOfBoundsException as attempting to insert at such an index is invalid.
index array contains duplicate indices	The list insertion will overwrite the previous element at this index, resolving the conflict according to the problem.
Large input size for nums and index, potentially exceeding memory limits	Consider using a data structure like a linked list or carefully managing memory when the input size is very large to prevent out-of-memory errors.
index array with all elements equal to 0	The resulting array will be a reversed version of the nums array.
nums array contains duplicate values with different corresponding indices	Each value is inserted at its specified index without interference from duplicate values.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for elements in the `nums` array and `index` array?
Can the `index` values be out of bounds for the target array at any point during the insertion process, or are they guaranteed to be valid?
If the `index` array contains duplicate indices, how should I handle those when inserting elements?
Are the lengths of the `nums` and `index` arrays guaranteed to be the same, and are they guaranteed to be non-empty?
What should I return if the input arrays are invalid, such as being null or having different lengths?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the first list.
Look at the corresponding position in the second list. This position tells you where to put the number in your new list.
Put the first number into the indicated position in the new list. If there was already a number in that position, shift it and all the following numbers to the right to make space.
Repeat this process for each subsequent number in the first list.
For each number in the first list, use the corresponding position in the second list to figure out where to put the new number in the new list.
Keep shifting numbers to the right as needed to insert the new number into the correct spot.
After processing all the numbers in the first list, the new list should be complete and have all the numbers in the requested order.

Code Implementation

def create_target_array(numbers, indices):    target_array = []
    for i in range(len(numbers)):        index_to_insert_at = indices[i]
        # Insert the number at the specified index.
        # This might require shifting existing elements.
        target_array = target_array[:index_to_insert_at] + [numbers[i]] + target_array[index_to_insert_at:]

    return target_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with an empty list-like structure that can grow as needed.
Take the first number from the numbers array and the corresponding position from the positions array.
Insert the number into the list at the indicated position.
Repeat the process for each number and position in the input arrays, inserting each number into the list at the specified position.
The list will automatically manage shifting existing elements to make space for the new insertions, maintaining the correct order.
Once you've processed all the numbers and positions, convert the list into the final array.
The resulting array will be in the target order, constructed by directly inserting elements into their correct spots.

Code Implementation

def create_target_array(numbers, positions):
    target_array = []

    # Iterate through the input arrays
    for index in range(len(numbers)):
        # Insert the number at the specified position
        target_array.insert(positions[index], numbers[index])

    return target_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty nums and index arrays	Return an empty array or throw an IllegalArgumentException if either input is null or empty.
nums and index arrays of different lengths	Throw an IllegalArgumentException because the index array needs a corresponding value from the nums array to be inserted.
index array contains negative indices	Throw an IllegalArgumentException since indices must be non-negative.
index array contains indices out of bounds (>= nums.length)	Throw an IndexOutOfBoundsException as attempting to insert at such an index is invalid.
index array contains duplicate indices	The list insertion will overwrite the previous element at this index, resolving the conflict according to the problem.
Large input size for nums and index, potentially exceeding memory limits	Consider using a data structure like a linked list or carefully managing memory when the input size is very large to prevent out-of-memory errors.
index array with all elements equal to 0	The resulting array will be a reversed version of the nums array.
nums array contains duplicate values with different corresponding indices	Each value is inserted at its specified index without interference from duplicate values.