Pascal's Triangle

Difficulty: Easy | Acceptance: 78.90% | Paid: No Topics: Array, Dynamic Programming

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1

• Examples
• Constraints
• Approach 1: Iterative Construction
• Approach 2: Mathematical Formula
• Approach 3: Recursive with Memoization

Examples

Example 1

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2

Input: numRows = 1
Output: [[1]]

Constraints

1 <= numRows <= 30

Iterative Construction

Intuition Build the triangle row by row, using the previous row to calculate the current row’s values.

Steps

• Initialize an empty result list
• For each row index from 0 to numRows-1:
  • Create a row filled with 1s (first and last elements are always 1)
  • For interior elements, sum the two elements from the previous row
  • Add the completed row to result
• Return the result

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        for i in range(numRows):
            row = [1] * (i + 1)
            for j in range(1, i):
                row[j] = result[i-1][j-1] + result[i-1][j]
            result.append(row)
        return result

Complexity

• Time: O(n²) where n is numRows
• Space: O(n²) for storing the result
• Notes: Most efficient and intuitive approach for this problem

Mathematical Formula

Intuition Each element in Pascal’s triangle can be calculated using the combination formula C(n, k) = n! / (k! × (n-k)!).

Steps

• For each row n from 0 to numRows-1:
  • Calculate each element using the combination formula
  • Use the property that C(n, k+1) = C(n, k) × (n-k) / (k+1) to avoid factorial calculations
  • Build the row and add to result
• Return the result

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        for n in range(numRows):
            row = []
            c = 1
            for k in range(n + 1):
                row.append(c)
                c = c * (n - k) // (k + 1)
            result.append(row)
        return result

Complexity

• Time: O(n²) where n is numRows
• Space: O(n²) for storing the result
• Notes: Useful when you need to compute individual elements without building the entire triangle

Recursive with Memoization

Intuition Recursively calculate each element as the sum of two elements from the previous row, using memoization to avoid redundant calculations.

Steps

• Create a memoization cache
• Define a helper function to get value at (row, col):
  • Base case: if col is 0 or equals row, return 1
  • Check cache first, return if found
  • Otherwise, recursively compute and cache the result
• Build each row by calling the helper function
• Return the result

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        memo = {}
        
        def getValue(row, col):
            if col == 0 or col == row:
                return 1
            if (row, col) in memo:
                return memo[(row, col)]
            memo[(row, col)] = getValue(row - 1, col - 1) + getValue(row - 1, col)
            return memo[(row, col)]
        
        result = []
        for i in range(numRows):
            row = []
            for j in range(i + 1):
                row.append(getValue(i, j))
            result.append(row)
        return result

Complexity

• Time: O(n²) where n is numRows
• Space: O(n²) for memoization and result
• Notes: Educational approach demonstrating recursion with memoization, though iterative is preferred