Code Logo

Pascal's Triangle II

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an integer rowIndex (0-indexed), return the rowIndex-th row of Pascal's triangle. For example, row 3 is [1,3,3,1]. Unlike generating the full triangle, this problem requires O(rowIndex) space by updating a single row array in place.

The DP approach starts with row = [1]. For each new level from 1 to rowIndex, update the row from right to left: row[j] = row[j] + row[j - 1]. Then append a 1 at the end. The right-to-left update ensures we use the previous row's values before they are overwritten.

At level i, the row has i+1 elements. Starting from index i-1 down to 1, each element becomes the sum of itself and the element to its left. Finally, append 1 for the last element. This in-place update pattern is a common space optimization for DP problems where each step depends on the previous step.

Edge cases include rowIndex = 0 (return [1]), rowIndex = 1 (return [1,1]), and rowIndex = 2 (return [1,2,1]).

The right-to-left update order is crucial for O(k) space. If we updated left-to-right, we would overwrite values needed for the next position. By going backwards, each element uses the untouched previous value from the same index before overwriting.

Example Input & Output

Example 1
Input
1
Output
[1,1]
Explanation

Second row [1,1].

Example 2
Input
2
Output
[1,2,1]
Explanation

Row 2.

Example 3
Input
0
Output
[1]
Explanation

First row is [1].

Example 4
Input
3
Output
[1,3,3,1]
Explanation

Row 3 (0-indexed) of Pascal's triangle.

Example 5
Input
4
Output
[1,4,6,4,1]
Explanation

Row 4.

Algorithm Flow

Recommendation Algorithm Flow for Pascal's Triangle II
Recommendation Algorithm Flow for Pascal's Triangle II

Solution Approach

Start with [1]. For each level, update row right-to-left: row[j] += row[j-1]. Append 1 at the end.

function solution(rowIndex) {
  var row = [1];
  for (var i = 1; i <= rowIndex; i++) {
    for (var j = row.length - 1; j >= 1; j--) {
      row[j] = row[j] + row[j - 1];
    }
    row.push(1);
  }
  return row;
}

Time O(k²), Space O(k).

Best Answers

java
class Solution {
    public int[] solution(int rowIndex) {
        int[] row = new int[rowIndex + 1];
        row[0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i; j >= 1; j--) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
}