Python 0118.py
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
result = [ [1] ]
for i in range(1, numRows):
row = []
for j in range(1, i):
row.append(result[i - 1][j - 1] + result[i - 1][j])
result.append([ 1 ] + row + [ 1 ])
return result
Difficulty
and has an acceptance rate of about 79% (3+ million submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
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 Solution class implements a method that constructs the first numRows rows of Pascal’s triangle. Each row is built from the values of the preceding row, preserving the combinatorial property that every interior element equals the sum of the two elements directly above it. The method returns a list of lists, where each inner list represents a single row of the triangle.
Key Steps
The algorithm begins by establishing the triangle with its topmost row, which is a single element 1.
result = [[1]]
A loop then iterates from the second row (index 1) up to the requested number of rows. For each iteration, a temporary list row is created to hold the interior values of the current row.
for i in range(1, numRows):
row = []
Inside this outer loop, a second loop runs over the interior positions of the new row, starting at index 1 and ending before the last index. Each interior element is computed by adding the two adjacent elements from the previous row, which are accessed via result[i - 1][j - 1] and result[i - 1][j]. The sum is appended to the temporary row list.
for j in range(1, i):
row.append(result[i - 1][j - 1] + result[i - 1][j])
After all interior elements have been generated, the complete row is formed by concatenating a leading 1, the interior row, and a trailing 1. This new row is then appended to the overall result collection.
result.append([1] + row + [1])
When the outer loop finishes, the method returns the fully constructed triangle.
return result
Edge Cases
When the caller requests a single row (numRows == 1), the outer loop does not execute because the range starts at 1 and ends before 1. Consequently, the method returns the initially created result, which correctly contains only the top row [[1]].
If numRows is greater than 1, the algorithm proceeds through the loops, generating each subsequent row based on the previously stored values. The inner loop’s range (range(1, i)) automatically yields an empty sequence for the second row (i == 1), resulting in an interior row that remains empty. The concatenation step then produces [1] + [] + [1], yielding the correct second row [1, 1]. This behavior demonstrates that the code gracefully handles rows that have no interior elements without requiring special-case logic.
Performance Optimizations
The implementation reuses the previously computed row (result[i - 1]) to calculate the next row, eliminating the need for recomputation of binomial coefficients from scratch. By building each new row incrementally and appending it directly to the result list, the algorithm avoids additional data structures or copying of large intermediate results.
The use of list concatenation ([1] + row + [1]) creates the final row in a single expression, which is more efficient than repeatedly inserting elements at the beginning or end of a list. Moreover, the inner loop only iterates over the interior positions (i - 1 iterations for row i), ensuring that the number of arithmetic operations grows proportionally to the total number of elements in the triangle rather than to the square of the row count.
By maintaining a single mutable result list that grows row by row, the method benefits from Python’s dynamic list resizing strategy, which amortizes allocation costs and keeps the overall runtime responsive even for larger values of numRows.
ELI5 - Simplified Explanation
Imagine building a tall tower out of blocks, one layer at a time. The code starts with just a single block at the very top. To make the next row, it looks at the blocks sitting above and adds their numbers together to see what the new block should be.
Every single row always starts with a one on the far left side and ends with a one on the far right side. When filling in the middle part of a row, the computer picks up the two blocks right above the empty spot, adds those numbers together, and puts the new total in the new space. It keeps doing this over and over again to make a growing triangle shape made of numbers until the tower is as tall as requested.
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 | C# | Rust | Java | JS | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| MemoryLimitExceeded | C++ | Python | ||||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | aylei | Rust | ||||||||||
| begeekmyfriend | C | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++ | |||||||||||
| bujosa | Rust | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| fengvyi | C++ | |||||||||||
| fpdjsns | C++ | |||||||||||
| gaosq0604 | Python | |||||||||||
| Garvit244 | Python | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C++ | |||||||||||
| lennylxx | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| luangong | C++ | |||||||||||
| martianoff | Scala | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| aylei | Rust | |||||||||||
| begeekmyfriend | C | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| bujosa | Rust | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| fengvyi | C++ | |||||||||||
| fpdjsns | C++ | |||||||||||
| gaosq0604 | Python | |||||||||||
| Garvit244 | Python | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C++ | |||||||||||
| lennylxx | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| luangong | C++ | |||||||||||
| martianoff | Scala | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ |
Similar Problems
- problem 119: Pascal's Triangle II
Solved On The Same Day
- problem 110: Balanced Binary Tree
- problem 111: Minimum Depth of Binary Tree
- problem 119: Pascal's Triangle II
- problem 228: Summary Ranges
- problem 530: Minimum Absolute Difference in BST
- problem 82: Remove Duplicates from Sorted List II
- problem 102: Binary Tree Level Order Traversal
- problem 103: Binary Tree Zigzag Level Order Traversal
- problem 105: Construct Binary Tree from Preorder and Inorder Traversal
- problem 106: Construct Binary Tree from Inorder and Postorder Traversal
- problem 107: Binary Tree Level Order Traversal II
- problem 109: Convert Sorted List to Binary Search Tree
- problem 117: Populating Next Right Pointers in Each Node II
- problem 128: Longest Consecutive Sequence
- problem 138: Copy List with Random Pointer
- problem 150: Evaluate Reverse Polish Notation
- problem 155: Min Stack
- problem 209: Minimum Size Subarray Sum
- problem 274: H-Index
- problem 380: Insert Delete GetRandom O(1)
- problem 427: Construct Quad Tree
- problem 452: Minimum Number of Arrows to Burst Balloons
- problem 30: Substring with Concatenation of All Words
- problem 37: Sudoku Solver
- problem 44: Wildcard Matching
- problem 1326: Minimum Number of Taps to Open to Water a Garden
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