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
Difficulty
and has an acceptance rate of about 87% (300k+ submissions).
Typical patterns to solve this problem:
- Array
- Simulation
AI Disclaimer
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.
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
numsandindexare empty, the initialresultremains an empty list, and the method returns it directly. - Insertion at the beginning - An index value of
0causes the sliceresult[:0]to be empty, so the new element becomes the first item in the list. - Insertion at the end - When
iequals the current length ofresult, the sliceresult[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
iis 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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Solved On The Same Day
- problem 1365: How Many Numbers Are Smaller Than the Current Number
- problem 1394: Find Lucky Integer in an Array
- problem 1758: Minimum Changes To Make Alternating Binary String
- problem 1357: Apply Discount Every n Orders
- problem 1362: Closest Divisors
- problem 1367: Linked List in Binary Tree
- problem 1386: Cinema Seat Allocation
- problem 1390: Four Divisors
- problem 1395: Count Number of Teams
- problem 1759: Count Number of Homogenous Substrings
Extra
- 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