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:

  \[ \begin{aligned}C_{n}^{m} &= \frac{n!}{m!(n-m)!} \\C_{n}^{m-1} &= \frac{n!}{(m-1)!(n-m+1)!}\end{aligned} \]

  Thus, we obtain the recurrence formula:

  \[ C_{n}^{m} = C_{n}^{m-1} \times \frac{n-m+1}{m} \]

  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
}