# Time complexity of generating Pascal’s triangle

Posted on

Problem

This is LeetCode question 118 Pascal’s triangle.

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

There is an example.

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

I am interested to know the time complexity of my solution, and how I can further improve it. I am thinking that the time complexity is O(mn) with n being `numRows` and m being the size of each row when calling my `AddToTriangle` function. Is there a way to condense this to a single loop and not a loop and another loop in a different function call? This is written in c#.

``````public IList<IList<int>> Generate(int numRows) {
IList<IList<int>> triangle = new List<IList<int>>();

for (int i = 1; i <= numRows; i++){
if (i > 2)
else if (i == 2)
triangle.Add(new List<int> { 1, 1 });
else
}
return triangle;
}

private void AddToTriangle(IList<IList<int>> triangle){//passing in triangle by reference
IList<int> row = triangle[triangle.Count - 1];//getting the last row in the List

triangle.Add(new List<int> { 1 });//creating a new row to append to
int index = triangle.Count - 1;//getting the last row to append to it
for (int i = 0; i < row.Count; i++){
int value = 1;
if (i + 1 < row.Count)
value = row[i] + row[i + 1];
}
}
``````

Solution

as far as I know, there is no solution so far on generating `Pascal's Triangle` in a single loop or doing it without a loop. (unless of course if the results are hard coded, which is impossible).

For the `Pascal's Triangle` there are two basic rules :

• Each row is an exponent of `11^n`
• First row is always `1`

these two basic rules would give you a better view on how to start solving it, and it would simplify your work further.

using these two rules, we would have something like (Thanks to @JohanduToit ):

``````public IEnumerable<IEnumerable<int>> GetPascalTriangle(int numRows)
{
for(int line = 0; line <= numRows + 1; line++)
{
var row = new List<int>();

int c = 1;

for(int i = 1; i <= line; i++)
{

c = c * ( line - i ) / i;
}

yield return row;
}
}
``````

Pascal’s triangle for a given N is going to have N rows, and the last row will have N entries.

For this reason, the time complexity will be O(N2).

In actuality, the triangle will have 1..N entries in N rows, so you’re really looking at the sum(1..N) total entries, which is something like N(N+1)/2. So it’s better than N-squared, but not much better.

You will have noticed there is a symmetry on each line. So you might be able to cache the generated numbers. But you’ll still have to format them for output, so you’re still going to process the same number of elements (albeit possibly really quickly).