# 119. Pascal’s Triangle I & II

Checkout problem description here.

For Pascal Tringle II -> Do it in O(rowIndex) Space.

*Pascal Triangle I*

*Solution*

`class Solution:`

def generate(self, numRows: int) -> List[List[int]]:

pascal=[[]]*numRows

for i in range(numRows):

pascal[i]=[0]*(i+1)

pascal[i][0],pascal[i][i]=1,1

for j in range(1,i):

pascal[i][j]=pascal[i-1][j-1]+pascal[i-1][j]

return(pascal)

Time: O(numRow²)

Space: O(numRow)

*Pascal Triangle II*

*Solution*

Approach 1: Brute Force

All the steps are same as we did in the Pascal Triangle , but we return last pascal row as the required asnwer.

`class Solution:`

def getRow(self, rowIndex: int) -> List[int]:

pascal=[[]]*(rowIndex+1)

for i in range(rowIndex+1):

pascal[i]=[0]*(i+1)

pascal[i][0],pascal[i][i]=1,1

for j in range(1,i):

pascal[i][j]=pascal[i-1][j-1]+pascal[i-1][j]

return(pascal[-1])

**Time: O(rowIndex²)**

**Space: O(row index²)**

Approach 2 :

**Optimizing Space to O(rowIndex)**

Using Binomial formula

value at nth row and rth Column is nCr

`class Solution:`

def combinatorial(self,n,r):

res=1

for i in range(0,r): #4c2= 4*3/1*2

res*=(n-i)

res//=(i+1)

return res

def getRow(self, rowIndex: int) -> List[int]:

result=[]

for i in range(rowIndex+1):

result.append(self.combinatorial(rowIndex,i))

return result

#Time O(rowIndex^2)

#Space O(rowIndex)

Time: O(rowIndex²)

Space: O(row index)

Approach 3:

Another way of doing it in optimized way is :

Say to get 3rd row we append 1 to previous row(2nd row ) and calculate the inner elements of new row(excluding left and right most 1).

1 2 1 -> 1 2 1 1

So add the elements from second last element till the index 1

ie

1 2 1 1-> 1 2 3 1->1 3 3 1

So we got the required result . This modification is performed in the same res list. So no extra space needed

`class Solution:`

def getRow(self, rowIndex: int) -> List[int]:

res=[1]

for i in range(1,rowIndex+1):

res.append(1)

for j in range(len(res)-2,0,-1):

res[j]=res[j-1]+res[j]

return(res)

Time: O(rowIndex²)

Space: O(row index)