Create Target Array in the Given Order - Practice Coding Problems

Create Target Array in the Given Order - Problem

Array Simulation Easy

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

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]

› Output: [0,4,1,3,2]

💡 Note: Step by step: Insert 0 at index 0: [0]. Insert 1 at index 1: [0,1]. Insert 2 at index 2: [0,1,2]. Insert 3 at index 2: [0,1,3,2]. Insert 4 at index 1: [0,4,1,3,2].

Example 2 — Minimum Size

$ Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]

› Output: [0,1,2,3,4]

💡 Note: Start with [1], then [1,2], [1,2,3], [1,2,3,4], finally insert 0 at position 0: [0,1,2,3,4].

Example 3 — All at Beginning

$ Input: nums = [1], index = [0]

› Output: [1]

💡 Note: Single element case: insert 1 at index 0 gives [1].

Constraints

1 ≤ nums.length, index.length ≤ 100
nums.length == index.length
0 ≤ nums[i] ≤ 100
0 ≤ index[i] ≤ i

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums=[0,1,2,3,4] and index=[0,1,2,2,1] specify values and positions

Sequential Insertion

Insert each nums[i] at position index[i], shifting existing elements

Final Target

Result array [0,4,1,3,2] after all insertions

Key Takeaway

🎯 Key Insight: Simulate the insertion process using a dynamic list that handles element shifting automatically

Asked in

🍎 Apple 8 M Microsoft 5

The key insight is to simulate the insertion process step by step. Use a dynamic list that supports insertion at arbitrary positions. For each element, insert it at the specified index, which automatically shifts existing elements. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with List Insertion	O(n²)	O(n)	Simulate the process by inserting each element at the specified index

Simulation with List Insertion — Algorithm Steps

Step 1: Initialize empty target list
Step 2: For each i, insert nums[i] at position index[i] in target
Step 3: Return the target list as array

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty target array

Insert Elements

For each (nums[i], index[i]), insert at position index[i]

Final Array

Return the constructed target array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* index, int indexSize, int* returnSize) {
    int* target = (int*)malloc(numsSize * sizeof(int));
    int targetSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // Shift elements to the right
        for (int j = targetSize; j > index[i]; j--) {
            target[j] = target[j-1];
        }
        target[index[i]] = nums[i];
        targetSize++;
    }
    
    *returnSize = targetSize;
    return target;
}

int* parseArray(char* str, int* size) {
    int* arr = (int*)malloc(1000 * sizeof(int));
    *size = 0;
    
    char* token = strtok(str + 1, ",]");
    while (token != NULL) {
        arr[*size] = atoi(token);
        (*size)++;
        token = strtok(NULL, ",]");
    }
    return arr;
}

int main() {
    char numsStr[10000], indexStr[10000];
    fgets(numsStr, sizeof(numsStr), stdin);
    fgets(indexStr, sizeof(indexStr), stdin);
    
    int numsSize, indexSize;
    int* nums = parseArray(numsStr, &numsSize);
    int* index = parseArray(indexStr, &indexSize);
    
    int returnSize;
    int* result = solution(nums, numsSize, index, indexSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(nums);
    free(index);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

n insertions, each insertion takes O(n) time to shift elements

⚠ Quadratic Growth

Space Complexity

O(n)

Target array stores n elements

⚡ Linearithmic Space

56.9K Views

Low Frequency

~10 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with List Insertion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler