Pascal\'s Triangle II Leetcode Solution

Problem Statement

In this problem we have been given Row index(i) of the Pascal Triangle. We have to create a linear array containing the values of the ith row and return it. Row index starts from 0.

We know that Pascal's triangle is a triangle where each number is the sum of the two numbers directly above it.

 

Example

rowIndex = 3

 

rowIndex = 0

 

As we know that each value in pascal's triangle is a binomial coefficient (nCr) where n is the row and r is the column index of that value.

 

We have discussed similar problem where we have to return all the rows from row index 0 to given row index of pascal's triangle here - Pascal Triangle Leetcode

 

But in this problem we only have to return single row whose index is given.

Here we will discuss three approaches for solution of this problem :

 

- Brute force

- Dynamic Programming

- Maths

 

Approach 1 (Brute Force Recursion)

We know that each number in this triangle is the sum of the two numbers directly above it. i.e

Num(row,col)= Num(row-1,col) + Num(row-1,col-1).

So we can repeatedly call the function Num(rowIndex,j) for each column index of that row, and return the formed list.

 

As we can see we have formulated recursive approach for finding Num(i,j). Now there are some base cases for that which are:

 

- Value at first row will be 1. So for row=0, Num(row, ... ) =0.

- Value at first column will be 1. So for col=0, Num( ... , col)=0.

- Last value of each row will be equal to 1. So for col=row=k, Num(k,k)=0.

 

www.tutorialcup.com/leetcode-solutions/pascals-triangle-i...

Done