Pascal's Triangle (Leet Code - 118)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 118. This is a Leet code problem named Pascal’s Triangle. We will solve it using python and it is the best space and time-optimized solution.

Question of Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In this, each number is the sum of the two numbers directly above it as shown:

What Is Pascal Triangle

It is a triangular array of integers in which the numbers at the end of each row are 1 and the remaining numbers are the sum of the closest two values in the preceding row. Probability, combinatorics, and algebra all employ this notion. Pascal’s triangle is used to calculate the probability of a coin flip, coefficients of binomial expansions in probability, and so on.

Example

Example 1

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

Example 2

Input: numRows = 1
Output: [[1]]

Constraints

1 <= numRows <= 30

Approach to solve Pascal’s Triangle

To create a this for the i^th row and j^th column we simply add j^th and (j-1)^th column of (i-1)^th row.

Algorithm

This method performs the following steps for a given input array:

Create an empty list to store a triangle named triangle.
Add the first row which is always 1
Repeat steps 4 to 9 till i in range numRows-1.
Create a new list named new to store row.
Append 1 as 1st element is always 1.
Repeat step 7 till j is in range 0 to i.
Add j^th element and (j+1)^th element of row i and append it into new[].
Append the last element of a row as 1
Append triangle by adding new in it.
Return triangle.

Python Code for Pascal’s Triangle

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        #list to store triangle 
        triangle = []
        #add first row which is always 1
        triangle.append([1])
        
        #run for loop for numRows-1
        for i in range(numRows-1):
            #list to store row
            #Initialize with 1 as 1st element is always 1
            new=[1]
            #run for loop to add 2 numbers of previous rows
            for j in range(0,i):
                new.append(triangle[i][j]+triangle[i][j+1])
            #add last element of row
            new.append(1)
            #add row in a triangle
            triangle.append(new)
            
        return triangle