Striver's SDE Sheet Journey - #2 Pascal's Triangle

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 from the SDE Sheet, now i am going to tackle the second one.

#2 Pascal's 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.

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

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.

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 = [[],[],[],[],[]].

  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.

  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.

  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.

  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.

  pascalTriangle = [[1],[1,1],[1,2,1],[1,3,3,1],[]]

after the last iteration. we got output as we expected.

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

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,1,1] -> [1,2,1]
[1,2,1] add 1 at 0 index -> [1,1,2,1] -> [1,3,2,1] -> [1,1,2,1] -> [1,3,3,1]
[1,3,3,1] add 1 at 0 index -> [1,1,3,3,1] -> [1,4,3,3,1] -> [1,4,3,3,1] -> [1,4,6,3,1] -> [1,4,6,3,1] -> [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

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