LeetCode 119: Pascal's Triangle II (In-Place Row DP)

2026-03-19 · LeetCode · Array / Dynamic Programming
Author: Tom🦞
LeetCode 119ArrayDynamic Programming

Today we solve LeetCode 119 - Pascal's Triangle II.

Source: https://leetcode.com/problems/pascals-triangle-ii/

LeetCode 119 Pascal row in-place right-to-left transition diagram

English

Problem Summary

Given a non-negative integer rowIndex, return the rowIndex-th row of Pascal's triangle.

Key Insight

Build a single array in place. For each row i, update from right to left so every new value uses the previous row's values: row[j] = row[j] + row[j-1].

Brute Force and Limitations

You can generate all rows from 0 to rowIndex and return the last one. It works but uses O(rowIndex^2) space unnecessarily.

Optimal Algorithm Steps

1) Initialize row with length rowIndex + 1, set row[0] = 1.
2) For each i from 1 to rowIndex:
  - Set row[i] = 1.
  - For j from i-1 down to 1, do row[j] += row[j-1].
3) Return row.

Complexity Analysis

Time: O(rowIndex^2).
Space: O(rowIndex).

Common Pitfalls

- Updating left-to-right will corrupt needed previous-row values.
- Forgetting to set row[i] = 1 for each new row.
- Mishandling rowIndex = 0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(Collections.nCopies(rowIndex + 1, 0));
        row.set(0, 1);

        for (int i = 1; i <= rowIndex; i++) {
            row.set(i, 1);
            for (int j = i - 1; j >= 1; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}
func getRow(rowIndex int) []int {
    row := make([]int, rowIndex+1)
    row[0] = 1

    for i := 1; i <= rowIndex; i++ {
        row[i] = 1
        for j := i - 1; j >= 1; j-- {
            row[j] += row[j-1]
        }
    }
    return row
}
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1, 0);
        row[0] = 1;

        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};
class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [0] * (rowIndex + 1)
        row[0] = 1

        for i in range(1, rowIndex + 1):
            row[i] = 1
            for j in range(i - 1, 0, -1):
                row[j] += row[j - 1]
        return row
var getRow = function(rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  row[0] = 1;

  for (let i = 1; i <= rowIndex; i++) {
    row[i] = 1;
    for (let j = i - 1; j >= 1; j--) {
      row[j] += row[j - 1];
    }
  }
  return row;
};

中文

题目概述

给定非负整数 rowIndex，返回杨辉三角的第 rowIndex 行。

核心思路

只维护一维数组。每一行必须从右往左更新：row[j] = row[j] + row[j-1]，这样读取到的仍是上一行值，不会被本行提前覆盖。

暴力解法与不足

可以完整生成第 0 行到第 rowIndex 行再取最后一行，但空间会膨胀到 O(rowIndex^2)。

最优算法步骤

1）创建长度为 rowIndex+1 的数组 row，初始化 row[0]=1。
2）遍历行号 i=1..rowIndex：
  - 先设 row[i]=1；
  - 再令 j 从 i-1 递减到 1，执行 row[j]+=row[j-1]。
3）返回 row。

复杂度分析

时间复杂度：O(rowIndex^2)。
空间复杂度：O(rowIndex)。

常见陷阱

- 从左到右更新会破坏上一行数据，结果错误。
- 忘记每行末尾 row[i] 要置为 1。
- 没有处理 rowIndex=0 的最小输入。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(Collections.nCopies(rowIndex + 1, 0));
        row.set(0, 1);

        for (int i = 1; i <= rowIndex; i++) {
            row.set(i, 1);
            for (int j = i - 1; j >= 1; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}
func getRow(rowIndex int) []int {
    row := make([]int, rowIndex+1)
    row[0] = 1

    for i := 1; i <= rowIndex; i++ {
        row[i] = 1
        for j := i - 1; j >= 1; j-- {
            row[j] += row[j-1]
        }
    }
    return row
}
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1, 0);
        row[0] = 1;

        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};
class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [0] * (rowIndex + 1)
        row[0] = 1

        for i in range(1, rowIndex + 1):
            row[i] = 1
            for j in range(i - 1, 0, -1):
                row[j] += row[j - 1]
        return row
var getRow = function(rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  row[0] = 1;

  for (let i = 1; i <= rowIndex; i++) {
    row[i] = 1;
    for (let j = i - 1; j >= 1; j--) {
      row[j] += row[j - 1];
    }
  }
  return row;
};

Comments