Given an integer numRows, return the first numRows rows of Pascal's triangle. Each row starts and ends with 1, and every inner number is the sum of the two numbers just above it in the previous row.
Example 1
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
In row 4, the 6 comes from
3 + 3 in the row above.Example 2
Input: numRows = 1
Output: [[1]]
Constraints
- 1 <= numRows <= 30
Hints
Frequently asked at: Amazon, Apple, Adobe, TCS, Wipro
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
You could compute every entry as a binomial coefficient C(i, j) with factorials, but factorials overflow fast and the work is repeated. Since each entry depends only on the two entries above it, building each row from the previous one is simple, exact and does constant work per number.
Algorithm
- Start with an empty list of rows.
- For
ifrom 0 tonumRows - 1, create a row ofi + 1ones. - For each inner index
j(1 toi - 1), setrow[j] = prev[j - 1] + prev[j]. - Append the row and continue; return all rows.
Time:
O(numRows^2)Space: O(numRows^2) for the outputInterview tip: A common follow-up is "return only row k using O(k) space" (Pascal's Triangle II). Update a single array from right to left so you do not overwrite values you still need.
class Solution: def generate(self, numRows: int) -> List[List[int]]: rows = [] for i in range(numRows): row = [1] * (i + 1) # edges are always 1 for j in range(1, i): row[j] = rows[i - 1][j - 1] + rows[i - 1][j] rows.append(row) return rowsCtrl + Enter runs the examples