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

#67 · #119 · Pascal's Triangle II(杨辉三角 II)

📌 Problem Statement & Constraints

Given an integer rowIndex, return the rowIndex-th (0-indexed) row of Pascal's triangle. Constraints: 0 <= rowIndex <= 33. The follow-up asks for O(rowIndex) extra space.

💡 Core Algorithmic Approaches

  1. Build the row in place from the end: row i has i + 1 entries, all initially 1.
  2. Updating from right to left with row[j] += row[j - 1] reads only values from the previous row, because row[j-1] has not yet been updated in this iteration.
  3. Going left to right would read already-updated values and produce wrong results.
  4. This yields O(rowIndex) space instead of the O(rowIndex^2) needed to store the whole triangle.

💻 Benchmark Python3 Implementation

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            # right-to-left so row[j-1] still holds the previous row's value
            for j in range(i - 1, 0, -1):
                row[j] += row[j - 1]
        return row

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(rowIndex^2): the total number of updates is 1 + 2 + ... + rowIndex.
💾 Space Complexity
O(rowIndex) for the single row, satisfying the follow-up requirement.

⚠️ Interview Pitfalls & Follow-ups

  • Updating left to right: row[j-1] would already hold the current row's value, corrupting the sum. This is the classic in-place DP direction bug.
  • Building the entire triangle: O(rowIndex^2) space, which the follow-up forbids.
  • Starting the outer loop at i = 1: row 1 is [1, 1] and needs no updates, so starting at 2 is correct and avoids a no-op pass.