1.
Introduction
2.
Problem Statement
3.
Approach: Dynamic programming
4.
Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Pascal Triangle

## Introduction

Pascal's Triangle, named after the French mathematician Blaise Pascal is a triangular array pattern of the binomial coefficients that arise in probability theory, combinatorics, and algebra.

Source: study tonight

As you can see in the above pattern, the triangle is constructed by placing the '1' along the left and right edges. The triangle can be formed from the top by adding the two numbers just above the left and right of each position. Therefore the third row is 1 2 1, and the fourth row will be 1 4 6 1, the fifth row is 1 5 10 10 5 1, and so on. For the first row, the coefficient for the expansion of (x+y)^0 = 1, the second row(1 1) the coefficient for (x+y)^1 = x+y, and so on.

Important Notes:

• The Pascals triangle elements can be found by finding the sum of the two adjoint elements in the preceding row.
• The sum of values in the nth row is 2n.

Also see, Euclid GCD Algorithm

## Problem Statement

We will be provided with a number n, for which we have to form a pascal triangle following its properties. The left and the right edges will be '1'. As you can see in the below picture, the first row contributes to building the second row by adding the elements of the first row. The third row has been built up with the help of the second row and so on. The below pascal triangle is for n=5 as we have 5 rows. Here we can observe that the number of entries in each row depends on the row number.

Resource: tutorial cup

For the ith row, there are i elements, where i≥1. jth element of the ith row is equal to i−1Cj−1 where1≤j≤i.

Other properties:

• The corner elements of each row are always equal to 1(i−1C0 and i−1Ci−1, i≥1).
• All the other (i,j) elements of the triangle (where i≥3 and 2≤j≤i−1) are equal to the sum of (i−1,j−1)th and (i−1,j)th element.

We can easily calculate the next row by iteratively adding adjacent values of the current row. This iterative process of generating a pascal triangle has been considered a dynamic programming approach wherein we construct each row based on the previous row.

Before stepping to the problem's solution- Pascal Triangle, try to give a shot by yourself.

## Approach: Dynamic programming

The dynamic Programming approach helps compute the next row based on the previous row.

The pseudo-code for that is as follows.

``````function pasca(N)

intialize a matrix dp[N][N] with 0

for i = 0 to N

dp[i][0]=dp[0][i]=1
endfor

for i = 1 to N
for j = 1 to N

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

endfor

endfor``````

Check out Longest Common Substring

## Complexity

Time Complexity: The time complexity for this DP approach is O(N*N), two nested loops.

Space Complexity: The space complexity will be O(N*N).

Check out this problem - Minimum Coin Change Problem

## FAQs

1). What do you mean by Dynamic Programming?

Dynamic programming is used to divide similar subproblems to reuse their results. Mostly, these algorithms are used for optimization.

2). What do you mean by Pascal Triangle?

The Pascal triangle is a triangular array of the binomial coefficients that arise in probability theory, combinatorics, and algebra.

3). What will be the time complexity for the DP approach?

The time complexity is O(n*n), where n is the number of rows.

## Key Takeaways

This blog has covered the following things:

What is the real meaning of the pascal triangle?

Properties of the pascal triangle.

Pseudocode of dynamic programming approach.

Pascal triangle is one of the most asked problems in product-based companies like Amazon and many more. You can practice problems similar to this, like  Find Kth row of Pascal's TrianglePascals Triangle, and many more.

Also, you can try to ace pattern patterns, which can also gear you up for the basic questions based on looping.

Once you are done with this, you can check out; Coding Ninjas Studio is a one-stop destination for various DSA questions typically asked in interviews to practice more such problems.

Keep Learning, Keep Growing!!!

Live masterclass