Pascal's Triangle II

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

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

## Pascal's Triangle Row

### Problem Description

Given an integer `rowIndex`, return the `rowIndex`th (0-indexed) row of the Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

### 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

### Brute Force Solution

A brute force solution involves generating the entire Pascal's triangle up to the `rowIndex`.  This requires storing all previous rows, which takes more space than necessary.

```python
def get_row_brute_force(row_index):
    triangle = []
    for i in range(row_index + 1):
        row = [1] * (i + 1)
        if i > 1:
            for j in range(1, i):
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    return triangle[row_index]

Optimal Solution

Since we only need the rowIndexth row, we can optimize space by only storing the current row. We can calculate each element in the row iteratively, using the values from the previous positions in the same row.

def get_row_optimal(row_index):
    row = [1] * (row_index + 1)
    for i in range(1, row_index):
        for j in range(row_index, i, -1):
            row[j] += row[j-1]
    return row

Example

For rowIndex = 3:

1. Initialize row = [1, 1, 1, 1]
2. i = 1
   • j = 3: row[3] = row[3] + row[2] = 1 + 1 = 2. row becomes [1, 1, 1, 2]
   • j = 2: row[2] = row[2] + row[1] = 1 + 1 = 2. row becomes [1, 1, 2, 2]
3. i = 2
   • j = 3: row[3] = row[3] + row[2] = 2 + 2 = 4. row becomes [1, 1, 2, 4]
   • j = 2: row[3] = row[2] + row[1] = 2 + 1 = 3. row becomes [1, 1, 3, 3]

Corrected code based on the above logic

def get_row(rowIndex):
    row = [1] * (rowIndex + 1)
    for i in range(1, rowIndex):
        for j in range(rowIndex, i, -1):
            row[j] = row[j] + row[j-1]
    return row

Big O Runtime Analysis

The outer loop runs rowIndex - 1 times. The inner loop runs from rowIndex down to i + 1. Therefore, the time complexity is approximately O(rowIndex^2). However, the prompt encourages an O(rowIndex) space complexity, so we should attempt to get the time complexity as close to linear time as possible. This is not realistically achievable given how the Pascal's triangle must be computed. The approach of using combinations can achieve near linear time, but that involves factorials which can quickly overflow unless done very carefully. The nested loops approach is a good balance of efficiency and simplicity.

Big O Space Usage Analysis

The optimal solution only uses an array of size rowIndex + 1 to store the current row. Therefore, the space complexity is O(rowIndex).

Edge Cases

• rowIndex = 0: Should return [1]
• rowIndex = 1: Should return [1, 1]
• rowIndex = 33: Should handle larger row indices correctly without integer overflow (within the integer limits of the language used).

These cases are all handled correctly by the provided optimal solution.