  # LeetCode 119. Pascal’s Triangle II (solution with images)

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

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: →

We can easily solve this problem by getting reference from previous example like below,

## LeetCode 118. Pascal’s Triangle

Those, who have not seen above example, please refer that one first.

In above problem, we need to find array of an array like below,

But over here, we just need to find a row array of given rowIndex.

First thing you can notice over here, that we need to append 1 in start and end position of row array.

We can achieve that by following way,

In previous problem LeetCode 118, we are creating rowArray as well, so it will be easy to do addition of previous row’s first two, second two’s additions,

Here, we just need to return only colArray, so we have taken only one array instead of two like previous leetcode, to reduce space complexity.

But, still we require previous row, so we can calculate addition of previous row’s elements.

To achieve that, we have taken one preList, which will keep record of previous array. So for every for loop, preList have previous array’s elements.

So, with use of preList, we can do addition and can append to current colList.

Such as,

At the end we just return preList, as for current iteration, preList is the current colList, for next iteration, colList will change.

Now, lets see full source code.

Code (Java): →

```                ```class Solution {
public List<Integer> getRow(int rowIndex) {

List<Integer> preList = null;
for(int i = 0; i <= rowIndex; i++){

List<Integer> colList = new ArrayList<>();
for(int j = 0; j <= i; j++){
if(j == 0 || i == j){
}else{
}
}
preList = colList;
}
return preList;
}
}```
```

Code (Python): →

```                ```class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
preList = []

for i in range(rowIndex+1):
colList = []
for j in range(i+1):

#First and last element is 1
if j == 0 or j == i:
colList.append(1)
else:
colList.append(preList[j-1]+preList[j])
preList = colList
return preList```
```

Time Complexity

Here, we have used two for loops, so total time complexity will be O(n²).

Space Complexity

Here, we have used only one array, other array is just for reference, so total space complexity will also be O(n).

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Please follow me on medium, I will post useful information like above.

Instagram → https://www.instagram.com/alexmurphyas8/

If I got something wrong? Let me in the comments. I would love to improve.

Join other developers and claim your FAUN account now!

Influence

Total Hits

Posts