Problem 1389

Abstract / Summary

Insert elements from a list into a new list at specific positions to form a target array.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1389.py

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        # nothing smart, just slicing ...
        result = []
        for i, n in zip(index, nums):
            result = result[:i] + [ n ] + result[i:]
        return result
7 lines | 279 bytes | submitted November 9, 2023 | GitHub   16% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 87% (300k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Simulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single method createTargetArray. The method receives two parallel lists, nums and index, and constructs a new list by inserting each element from nums into a growing result list at the position specified by the corresponding entry in index. The algorithm proceeds in a single forward pass, building the target array incrementally.

Core Logic

The method begins by creating an empty list that will hold the intermediate and final results.

result = []

A for loop iterates over the paired elements of index and nums using zip. For each pair, the current element n is inserted into result at position i. The insertion is performed by slicing the existing list into two parts, inserting the new element between them, and concatenating the three pieces back together.

for i, n in zip(index, nums):
    result = result[:i] + [n] + result[i:]

Finally, the fully constructed list is returned.

return result

The use of zip(index, nums) guarantees that the two input sequences are traversed in lockstep, preserving the intended correspondence between values and insertion positions.

Edge Cases Handled

The algorithm naturally accommodates several boundary conditions without additional checks:

  • Empty input - When both nums and index are empty, the initial result remains an empty list, and the method returns it directly.
  • Insertion at the beginning - An index value of 0 causes the slice result[:0] to be empty, so the new element becomes the first item in the list.
  • Insertion at the end - When i equals the current length of result, the slice result[i:] yields an empty list, effectively appending the new element.
  • Repeated indices - If the same index appears multiple times, each subsequent insertion pushes previously inserted elements to the right, preserving the order dictated by the input sequences.
  • Maximum index - The algorithm assumes that each i is a valid position within the range [0, len(result)] at the moment of insertion, which aligns with the problem constraints.

Performance Characteristics

The implementation leverages Python’s list slicing and concatenation to perform each insertion. By constructing a new list from three components- the prefix before the insertion point, a single-element list containing the new value, and the suffix after the insertion point- the code avoids explicit element-wise shifting loops. This approach benefits from the underlying C-level optimizations of slice operations and list concatenation, which can be faster than manually moving elements in pure Python.

Because the method processes the input arrays in a single pass, the overall control flow is straightforward and incurs minimal overhead beyond the slice operations themselves. The use of zip ensures that the two input lists are traversed together without the need for index management, contributing to a clean and efficient iteration pattern.

written by openai gpt

ELI5 - Simplified Explanation

Imagine the computer is preparing a special train for a parade. There are two lists of instructions. One list tells the computer which toys to pick up, and the other list tells the computer exactly where each toy belongs in the train.

The computer starts with an empty train track that has no wagons on it yet. It looks at the first toy and then checks the spot number where that toy should go. If the spot is new, the computer adds the toy. If the train already has other toys, the computer gently slides the wagons apart at that spot to make a new empty space. Then, it places the toy into that gap.

It keeps doing this for every toy in the pile, moving the existing toys around to make sure everyone lands in their perfect numbered spot. By the time the computer goes through all the instructions, all the toys are lined up in the order the list asked for, like a perfectly organized, colorful toy train ready to start its journey along the track.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.85 | σ = 1.38

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
MacJim C++
muhammadfarhankt Go
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
MacJim C++
muhammadfarhankt Go
varunu28 Java
YuriSpiridonov Python
32 links | 21 authors | 9 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

11 solutions   November 9, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality