Time complexity of generating Pascal's triangle

Question

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)
            AddToTriangle(triangle);
        else if (i == 2)
            triangle.Add(new List<int> { 1, 1 });
        else
            triangle.Add(new List<int> { 1 });
    }
    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];
        triangle[index].Add(value);
    }
}

Answer 1

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++)
        {
            row.Add(c);

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

        yield return row;
    }
}

Answer 2

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(N²).

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).