119. Pascal's Triangle II

Problem

Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

Notice that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

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

Problem Summary

Given a non-negative index k, where k ≤ 33, return the kth row of Pascal's triangle.

Solution Approach

• The triangle in the problem is Pascal's triangle, and each number is a coefficient in the binomial expansion of (a+b)^n. The problem requires us to use only O(k) space. Therefore, we need to find the recurrence relation between adjacent terms. From combinatorics, we know:

  {{< katex display >}} \begin{aligned}C_{n}^{m} &= \frac{n!}{m!(n-m)!} \C_{n}^{m-1} &= \frac{n!}{(m-1)!(n-m+1)!}\end{aligned} {{< /katex>}}

  Thus, we obtain the recurrence formula:

  {{< katex display >}} C_{n}^{m} = C_{n}^{m-1} \times \frac{n-m+1}{m} {{< /katex>}}

  Using this recurrence formula, the space complexity can be optimized to O(k)

Code

package leetcode

func getRow(rowIndex int) []int {
	row := make([]int, rowIndex+1)
	row[0] = 1
	for i := 1; i <= rowIndex; i++ {
		row[i] = row[i-1] * (rowIndex - i + 1) / i
	}
	return row
}