Striver's SDE Sheet Journey - #2 Pascal's Triangle
Tags: beginners, dsa, programming, java
Published: 2021-12-15 08:59:38

Hi👋,devs.

I have started a Journey called **Striver's SDE Sheet Journey** and in this journey, I have successfully solved the first problem [#1](https://dev.to/sachin26/strivers-sde-sheet-journey-1-set-matrix-zeroes-4l68) from the SDE Sheet, now i am going to tackle the second one.

## [#2 Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)

In this problem we have given a Integer number or `numRows` and we need to return first `numRows` of pascal's triangle as a 2D array.

```javascript
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
![pascal's triangle](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/khh7vh77tkhyde4liq70.png)


as you can see in the fig,

- in Pascal's Triangle, each number is the sum of two numbers directly above it.

- each row's first & last value is 1.

after getting some data points of the Pascal Triangle pattern. I got an idea to tackle this problem.
let's discuss my idea step by step.


---


> _my approach_

**1.** initialize a `numRows` size of the array `pascalTriangle` that holds a list of Integer `row`.

**2.** run a loop from `numRow = 1` to `numRows`.

>> **2.1** inside a loop we again create an array `row` with a size of iteration number or `numRow` and fill it with **1's**.
e.g. `numRow = 3` then `row = [1,1,1]`

>> **2.2** run a loop from `i = 1` to `numRow - 1`.

>> >> **2.2.1** compute the row's value from previous row values. (we can get the previous row from `pascalTriangle` array)
 e.g. `value = preRow[i-1] + preRow[i]`

>> >> **2.2.1** set the computed value to the `row` array at index i.

>> **2.3** add `row` array to `pascalTriangle` array.

**3.** return `pascalTriangle` array.

**4.** end.

> Let's do a Dry Run this approach on a simple example.

```javascript
Input: numRows = 5
expected Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```

**step-1** initialized an array of size `numRows` called `pascalTriangle = [[],[],[],[],[]]`.

```javascript
  pascalTriangle = [[],[],[],[],[]]
```
**step-2** run a loop from `numRow = 1` to `numRows`.
**at numRow = 1**
> **1.** initialized an array size of `numRow` and fill with  **1's**.
`row = [1]`

> **2.** run a loop from `i = 1` to `numRow - 1`.
> > **at i = 1** => ( 1 < 1-1 ) loop condition does not satisfy the running criteria so that this loop does not get executed.

> **3.** add `row` array to `pascalTriangle` array.
```javascript
  pascalTriangle = [[1],[],[],[],[]]
```
**at numRow  = 2**
> **1.** initialized an array size of `numRow` and fill with  **1's**.
 `row = [1,1]`
> **2.** run loop.
> > **at i = 1** => ( 1 < 2-1 ) loop condition does not satisfy the running criteria

> **3.** add `row` array to `pascalTriangle` array.
```javascript
  pascalTriangle = [[1],[1,1],[],[],[]]
```
**at numRow  = 3**
> **1.** initialized an array size of `numRow` and fill with  **1's** e.g. `row = [1,1,1]`
> **2.** run loop.
> >  **at i = 1** => ( 1 < 3-1 ) loop condition satisfy the running criteria then,
> > > **1.** calculate the value from the previous row.
`value = priRow[1-1] + preRow[1]` => `2 = 1 + 1`
> > > **2.** set `value` to `row` array at 1 index.
`row = [1,2,1]`

> > **at i = 2** => ( 2 < 3-1 ) loop condition does not satisfy the running criteria then loop end.

> **3.** add to `row = [1,2,1]` to `pascalTriangle` array.
```javascript
  pascalTriangle = [[1],[1,1],[1,2,1],[],[]]
```
**at numRow  = 4**
> **1.** initialized an array size of `numRow` and fill with  **1's** e.g. `row = [1,1,1,1]`
> **2.** run loop
> > **at i = 1** => ( 1 < 4-1 ) loop condition satisfy the running criteria then,
> > > **1.**  calculate the value from the previous row.
`value = priRow[1-1] + preRow[1]` => `3 = 1 + 2`
> > > **2.** set `value` to `row` array at 1 index.
set `value` to `row` array at i index,`row = [1,3,1,1]`

> > **at i = 2** => ( 2 < 4-1 ) loop condition satisfy the running criteria then,
> > > **1.** calculate the value from the previous row.
`value = priRow[2-1] + preRow[2]` => `3 = 2 + 1`
> > > **2.** set `value` to `row` array at 1 index.
`row = [1,3,3,1]`

> > **at i = 3** => ( 3 < 3-1 ) loop condition does not satisfy the running criteria then loop end.

> **3.** add to `row = [1,3,3,1]` to `pascalTriangle` array.

```javascript
  pascalTriangle = [[1],[1,1],[1,2,1],[1,3,3,1],[]]
```
after the last iteration. we got output as we expected.

 ```javascript
  pascalTriangle = [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```

> _Java_

```java
import java.util.ArrayList;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        // step-1 initialized an array that holds a list of Integer
        List<List<Integer>> pascalTriangle = new ArrayList<List<Integer>>(numRows);
      
         // step-2 run a loop from 1 to numRow 
        for(int numRow=1; numRow<=numRows;numRow++){
            
         // step-2.1 initialized a array & filled with 1's
          List<Integer> row = new ArrayList<Integer>(Collections.nCopies(numRow,1));
            
           // step2.2 run a loop from 1 to numRow -1
            for(int i=1;i<numRow-1;i++){
                // get previous row array from pascalTriangle array
                List<Integer> preRow =  pascalTriangle.get(numRow-2);
                
                // step-2.2.1 calculate value from previous row array
                int value = preRow.get(i-1) + preRow.get(i);
                
                // step-2.2.2 set value at index i
                row.set(i,value);
            }
           
            // step-2.3 add the row array to pascalTriangle array
            pascalTriangle.add(row);
        }
        
        // step-3 return the pascalTriangle array
        return pascalTriangle;
        
    }
}

// end
```

> Other Approaches

### _Algo #1_
_in this approach we can compute the Triangle's row array by adding **1** at index 0._

`example:-`

`[1,1]` add 1 at 0 index -> [1,<u>**1**,**1**</u>] -> `[1,2,1]`
`[1,2,1]` add 1 at 0 index -> [1,<u>**1**,**2**</u>,1] -> `[1,3,2,1]` -> [1,1,<u>**2,1**</u>] -> `[1,3,3,1]`
`[1,3,3,1]` add 1 at 0 index -> [1,<u>**1,3**</u>,3,1] -> `[1,4,3,3,1]` -> [1,4,<u>**3**,**3**</u>,1] -> `[1,4,6,3,1]` -> [1,4,6,<u>**3,1**</u>] -> `[1,4,6,4,1]`

> let's understand this approach step by step.

**step-1.** initialize two arrays `pascalTri` and `row`.
**step-2.** run a loop from `numRow = 1` to `numRows`.
> **1.** add **1** to `row` array at index 0.
> **2.** run a loop from `i = 1` to `row.size -1`.
>  > **1.** update `row` array value.
e.g. `row.set(i,row.get(i) + row.get(i+1))`

> **3.** add a copy of the `row` array to `pascalTri` array.

**step-3** return `pascalTri` array.

**step-4** end.

> Java

```java
public class Solution {
public List<List<Integer>> generate(int numRows)
{
    // initialize two Lists
	List<List<Integer>> pascalTri = new ArrayList<List<Integer>>();
	ArrayList<Integer> row = new ArrayList<Integer>();
    
    // run 1 to numRows
	for(int numRow=1;numRow<=numRows;numRow++)
	{
        // add 1 at index 0
		row.add(0, 1);
 
        // update row value
		for(int i=1;i<row.size()-1;i++)
			row.set(i, row.get(i)+row.get(i+1));
        
        // add a copy of row instance
		pascalTri.add(new ArrayList<Integer>(row));
	}
	return pascalTri;
	
  }
    
}
```

> _Time Complexity_

we are initializing a row array and traversing the row's element for updating the cell.
so that time complexity : **O(numRows*numRows)**


> _Space Complexity_

so we are initilaizing a 2D matrix (`pascalTri` and `row`).
then space complexity : **O(pascalTri*row)**

_Thank you for reading this article. if you have any query please share them in the comment box_