Domain 1EasyCORE

Pascal's Triangle II

The problem asks us to return the `rowIndex`-th row of Pascal's triangle. Pascal's triangle is a triangular array of the binomial coefficients. Each number in the triangle is the sum of the two numbers directly above it.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

119. Pascal’s Triangle II

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.5%


Problem Breakdown

The problem asks us to return the rowIndex-th row of Pascal’s triangle. Pascal’s triangle is a triangular array of the binomial coefficients. Each number in the triangle is the sum of the two numbers directly above it.

Inputs:

  • An integer rowIndex (0-indexed), which specifies which row of Pascal’s triangle to return.

Outputs:

  • A list of integers representing the rowIndex-th row of Pascal’s triangle.

Implicit Constraints or Tricky Edge Cases:

  • The input rowIndex can be as large as 33, so the solution should be efficient in terms of both time and space.
  • The first row (rowIndex = 0) is [1].
  • The second row (rowIndex = 1) is [1, 1].

Intuition

A brute-force approach would involve generating all rows up to rowIndex using a nested loop. However, this approach has a time complexity of O(rowIndex^2) and uses O(rowIndex^2) space, which is inefficient given the constraints.

The key insight is that each row in Pascal’s triangle can be generated from the previous row by summing adjacent elements. This allows us to build the triangle row by row using only O(rowIndex) extra space.

Approach

  1. Initialize an array row with all elements set to 1, representing the first row of Pascal’s triangle.
  2. For each subsequent row up to rowIndex, update the elements in place:
    • Start from the second last element and move towards the first element.
    • Each element at position j is updated to be the sum of itself and the element directly above it (position j-1).
  3. After processing all rows, the array row will contain the rowIndex-th row of Pascal’s triangle.

Complexity Analysis

  • Time Complexity: O(rowIndex^2) because we need to update each element in the row for each row up to rowIndex.
  • Space Complexity: O(rowIndex) because we only store one row at a time.

Solution

def getRow(rowIndex: int) -> List[int]:
    # Initialize the first row of Pascal's triangle
    row = [1] * (rowIndex + 1)
    
    # Generate each row up to rowIndex
    for i in range(1, rowIndex + 1):
        # Update the row from right to left
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]
    
    return row

Edge Cases Handled

  • rowIndex = 0: The function returns [1], which is the first row of Pascal’s triangle.
  • rowIndex = 1: The function returns [1, 1], which is the second row of Pascal’s triangle.
  • rowIndex = 33: The function efficiently computes the 33rd row using O(rowIndex) space.