💬 Discord
Sign In
NeetCode #41LC-118EasyArrays & Hashing
← Back to All Problems

#41 · #118 · Pascal's Triangle(杨辉三角)

📌 Problem Statement & Constraints

Given an integer numRows, return the first numRows rows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Constraints: 1 <= numRows <= 30.

💡 Core Algorithmic Approaches

  1. Every row starts and ends with 1.
  2. Interior elements are the sum of the previous row's adjacent pairs: row[j] = prev[j-1] + prev[j].
  3. Build each row from the previous one, so the work per row is proportional to its length.
  4. The total number of elements is numRows * (numRows + 1) / 2, which sets both the time and space bounds.

💻 Benchmark Python3 Implementation

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]                        # row 0
        for _ in range(1, numRows):
            prev = res[-1]
            row = [1]
            for j in range(1, len(prev)):
                row.append(prev[j - 1] + prev[j])   # interior sums
            row.append(1)
            res.append(row)
        return res


# Same idea, written with the classic boundary padding
class Solution2:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(numRows):
            row = [1] * (i + 1)
            for j in range(1, i):
                row[j] = res[i - 1][j - 1] + res[i - 1][j]
            res.append(row)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(numRows^2): the total number of generated elements is quadratic in numRows.
💾 Space Complexity
O(numRows^2) for the returned triangle, which is unavoidable since the output itself is that large.

⚠️ Interview Pitfalls & Follow-ups

  • Building rows of the wrong length: row i has exactly i + 1 elements.
  • Using the current row instead of the previous row for the sums: row[j] must read from res[i-1], otherwise the already-updated values contaminate the result.
  • Indexing prev[j+1] for the last interior element: the last element of the previous row is prev[-1], and the interior loop must stop before it.