LeetCode: Pascal's Triangle C# https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/601/



In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

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


Please review for performance.

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace RecurssionQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/601/
    /// &lt;/summary&gt;
    [TestClass]
    public class PascalTriangleTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            IList&lt;IList&lt;int&gt;&gt; result = PascalTriangle.Generate(5);
            IList&lt;IList&lt;int&gt;&gt; expected = new List&lt;IList&lt;int&gt;&gt;();
            expected.Add(new List&lt;int&gt; { 1 });
            expected.Add(new List&lt;int&gt; { 1, 1 });
            expected.Add(new List&lt;int&gt; { 1, 2, 1 });
            expected.Add(new List&lt;int&gt; { 1, 3, 3, 1 });
            expected.Add(new List&lt;int&gt; { 1, 4, 6, 4, 1 });
            for (int i = 0; i &lt; expected.Count; i++)
            {
               CollectionAssert.AreEqual(expected[i].ToList(), result[i].ToList());
            }
        }
    }

    public class PascalTriangle
    {
        public static IList&lt;IList&lt;int&gt;&gt; Generate(int numRows)
        {
            IList&lt;IList&lt;int&gt;&gt; result = new List&lt;IList&lt;int&gt;&gt;();
            if (numRows == 0)
            {
                return result;
            }
            List&lt;int&gt; row = new List&lt;int&gt;();
            row.Add(1);
            result.Add(row);
            if (numRows == 1)
            {
                return result;
            }

            for (int i = 1; i &lt; numRows; i++)
            {
                var prevRow = result[i - 1];
                row = new List&lt;int&gt;();
                row.Add(1);
                for (int j = 0; j &lt; prevRow.Count - 1; j++)
                {
                    row.Add(prevRow[j] + prevRow[j + 1]);
                }
                row.Add(1);
                result.Add(row);
            }
            return result;
        }
    }
}
Something I ran into while making my own implementation:

After 34 rows, the highest number in the row will be two 1166803110s. Adding these for row 35 exceeds the maximum value for ints, resulting in integer-overflow.

You might consider putting the line that does the addition into a checked block, so that an OverflowException is properly thrown:

for (int j = 0; j &lt; prevRow.Count - 1; j++)
{
     checked 
     {
         row.Add(prevRow[j] + prevRow[j + 1]);
     }
}


As mentioned in the comments, the values in the rows grow almost exponentially. This means that switching from int to long as datatype in the lists will only roughly double the amount of rows that can be supported before these too overflow.