# LeetCode - Pascal's Triangle II

## Problem statement

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

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

Problem statement taken from: https://leetcode.com/problems/pascals-triangle-ii

**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`

### Explanation

#### Generate Pascal Triangle and return the row

The problem is almost similar to our previous blog, where we generated the Pascals Triangle. Here, we have to return the particular row of the triangle instead of generating it.

We can use the 3rd approach as mentioned in the Pascals Triangle blog and return the rowIndexth.

The time-complexity of this approach is **O(N^2)**, and space complexity is **O(1)**.

#### O(N) solution

If we carefully observe the above approach, we need not generate the full pascals triangle and directly compute the coefficients.

Let's jump to the algorithm to understand it better.

```
- initialize result array
- set c = 1
// push c into result
result.push(c)
- loop for i = 1; i <= rowIndex; i++
// generate the coefficient using the below formula
- c = c * (rowIndex + 1 - i) / i
// push the generated coefficient in the result
- result.push(c)
- return result
```

The time-complexity of this approach is **O(N)**, and space complexity is **O(1)**.

Let's check our algorithm in **C++**, **Golang**, and **Javascript**.

#### C++ solution

```
class Solution {
public:
vector<int> pascalRow(int rowIndex) {
vector<int> result;
long int c = 1;
result.push_back(c);
for(int i = 1; i <= rowIndex; i++) {
c = c*(rowIndex + 1 - i)/i;
result.push_back(c);
}
return result;
}
vector<int> getRow(int rowIndex) {
return pascalRow(rowIndex);
}
};
```

#### Golang solution

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

#### Javascript solution

```
var pascalRow = function(rowIndex) {
let result = [];
let c = 1;
result.push(c);
for(let i = 1; i <= rowIndex; i++) {
c = c*(rowIndex + 1 - i)/i;
result.push(c);
}
return result;
}
var getRow = function(rowIndex) {
return pascalRow(rowIndex);
};
```

#### Dry Run

Let's dry-run our algorithm for **Example 1**.

```
Input: rowIndex = 3
Step 1: vector<int> result
int c = 1
Step 2: result.push_back(c)
result = [1]
Step 3: loop for i = 1; i <= rowIndex
1 <= 3
true
c = c * (rowIndex + 1 - i) / i
= 1 * (3 + 1 - 1) / 1
= 1 * 3
= 3
result.push_back(c)
result = [1, 3]
i++
i = 2
Step 4: loop for i <= rowIndex
2 <= 3
true
c = c * (rowIndex + 1 - i) / i
= 3 * (3 + 1 - 2) / 2
= 3 * 1
= 3
result.push_back(c)
result = [1, 3, 3]
i++
i = 3
Step 5: loop for i <= rowIndex
3 <= 3
true
c = c * (rowIndex + 1 - i) / i
= 3 * (3 + 1 - 3) / 3
= 3 * 1 / 3
= 1
result.push_back(c)
result = [1, 3, 3, 1]
i++
i = 4
Step 6: loop for i <= rowIndex
4 <= 3
false
Step 7: return result
We return the result as [1, 3, 3, 1].
```