Pascal Triangle

Problem: Write a method to generate the first n rows of Pascal Triangle where n is given as an input.

Example:

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

Approach: Nothing to explain here as it is fairly straight forward. Please look at the implementation for understanding the approach.

Implementation in C#:

    public IList<IList<int>> Generate(int numRows) 

    {

        List<IList<int>> result = new List<IList<int>>();

        if (numRows <= 0)

        {

            return result;

        }

        result.Add(new List<int>{ 1 });

        for (int i = 1; i < numRows; ++i)

        {

            result.Add(new List<int>());

            result[i].Add(1);

            for (int j = 1; j < i; ++j)

            {

                result[i].Add(result[i - 1][j] + result[i - 1][j - 1]);

            }  

            result[i].Add(1);

        }        

        return result;        

    }

Complexity: O(n^2)