119. Pascal's Triangle II

Description of Problem

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

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

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

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solution

Code (Rust)

impl Solution {
    pub fn get_row(row_index: i32) -> Vec<i32> {
        let row_index = row_index as usize;
        let mut curr = vec![0; row_index + 1];
        for n in 0..=row_index {
            // Do not remove `.rev()` due to data dependency.
            for r in (0..=n).rev() {
                curr[r] = if r == 0 || r == n { 1 } else { curr[r-1] + curr[r]};
            }
        }
        return curr;
    }
}

Complexity

Time Complexity

• \( T(row\_index) = \Theta(row\_index)\)
  • 1+2+3+4+...+row_index

Auxiliary Space

• \(S(row\_index) = O(row\_index)\)