Pascal's Triangle II

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

Given an integer rowIndex, return the rowIndexth (0-indexed) row 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
• Full Triangle Construction
• Space Optimized DP
• Mathematical Formula

Examples

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints

0 <= rowIndex <= 33

Full Triangle Construction

Intuition Build the entire Pascal’s triangle row by row up to the target row, then return the last row.

Steps

• Initialize an empty list to store all rows
• For each row index from 0 to rowIndex:
  • Create a row filled with 1s
  • Update middle elements using values from the previous row
  • Add the row to the triangle
• Return the row at the given index

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

Complexity

• Time: O(rowIndex²)
• Space: O(rowIndex²)
• Notes: Simple but uses extra space to store all previous rows

Space Optimized DP

Intuition Use a single array and update it in place from right to left, avoiding the need to store all previous rows.

Steps

• Initialize a row array with all 1s
• For each row level from 1 to rowIndex-1:
  • Update elements from right to left using the sum of current and previous values
• Return the final row

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(1, rowIndex):
            for j in range(i, 0, -1):
                row[j] += row[j-1]
        return row

Complexity

• Time: O(rowIndex²)
• Space: O(rowIndex)
• Notes: Optimal space complexity using in-place updates

Mathematical Formula

Intuition Each element in Pascal’s triangle is a binomial coefficient C(n, k), which can be computed iteratively using the relation C(n, k) = C(n, k-1) × (n-k+1) / k.

Steps

• Initialize a row array with all 1s
• For each position from 1 to rowIndex-1:
  • Compute the value using the previous value and the binomial coefficient formula
• Return the final row

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(1, rowIndex):
            row[i] = row[i-1] * (rowIndex - i + 1) // i
        return row

Complexity

• Time: O(rowIndex)
• Space: O(rowIndex)
• Notes: Most efficient approach with linear time complexity