LeetCode: Pascal's Triangle C#

Question

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

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

            for (int i = 1; i < numRows; i++)
            {
                var prevRow = result[i - 1];
                row = new List<int>();
                row.Add(1);
                for (int j = 0; j < prevRow.Count - 1; j++)
                {
                    row.Add(prevRow[j] + prevRow[j + 1]);
                }
                row.Add(1);
                result.Add(row);
            }
            return result;
        }
    }
}

Answer 1

I wouldn't bother with the numRows == 1 special case (it is redundant and just adds code), but you should be checking that numRows >= 0 and throwing an argument exception if it is not (and ideally testing for that as well); currently it treats numRows < 0 as numRows == 1 which makes no sense at all.

---

As always, this would benefit from inline documentation, qualifying what the method does, and what it expects of the caller (e.g. a non-negative number of rows).

---

You might consider var for result and row. Within the method it is fine for result to be List<Ilist<int>>, and will have the nice side-effect of removing a little unnecessary indirection (I'm assuming the CLR won't/can't optimise that away).

---

You might consider using the List(int) constructor to improve the memory characteristics of your method, since you know in an advance how large each list will be. Alternatively, if performance matters enough that you will actually benchmark this, then consider an immutable return type (IReadOnlyList<IReadOnlyList<int>>) and use arrays directly.

---

I don't like the spacing in your code: I would at the very least separate the == 0 and == 1 cases with an empty line. They are logically distinct, and having them mushed together fails to convey this.

---

TestMethod1 is a poor name, and the text fails to check that the length of the output is correct (it could return 6 rows and you'd never know). Tests for edge cases (0, 1) and invalid arguments (-1) are important.

---

Your row variable is all over the place. I would put it inside the loop, and add the first one directly as result.Add(new List<int>() { 1 }). As it is, you could use prevRow = row, which would avoid a lookup.

---

Again, if you really care about performance, you should be benchmarking it with a realistic use case (unfortunately those don't exist for such tasks, and optimisation is basically pointless), but you could avoid making 2 lookups from the previous row for the 'inner' entries. Something like this should work:

// inside for (i...)
int left = 0;
for (int j = 0; j < i - 1; j++)
{
    int right = prevRow[j];
    row.Add(left + right);
    left = right;
}
row.Add(1);
results.Add(row)

This would also allow you to remove the numRows == 1 special case, which would be amusing. Alternatively you could start at j = 1 and bake the row.Add(1) first entry.

---

You might also consider a lazy version producing an IEnumerable<IReadOnlyList<int>>: this would probably be slower than a non-lazy version for small inputs, but would enable you to handle larger triangles when you would otherwise run out of memory (would be linear rather than quadratic), and the improved memory characteristics may even lead to better performance.

Answer 2

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

Answer 3

VisualMelon already said everything I wanted to say and more, but at his request, here are the variants I tested. Using list capacity is about 20-50% faster (less gain for higher numbers of rows), while using arrays is consistently more than 80% faster. Left-value caching is about 10-20% faster, and making use of the reflective nature of rows (as mentioned by dfhwze) yields another 10% improvement.

It's also possible to calculate the contents of a row without first calculating all previous rows. It's roughly twice as slow per row because it involves multiplication and division instead of addition, but it's a lot more efficient if you only need a specific row.

// Original approach, modified to cache the previous row's left value:
public static IList<IList<int>> Generate_Improved(int numRows)
{
    IList<IList<int>> result = new List<IList<int>>();
    if (numRows == 0)
    {
        return result;
    }
    List<int> row = new List<int>();
    row.Add(1);
    result.Add(row);
    if (numRows == 1)
    {
        return result;
    }

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        row = new List<int>();
        var left = 0;
        for (int j = 0; j < prevRow.Count; j++)
        {
            int right = prevRow[j];
            row.Add(left + right);
            left = right;
        }
        row.Add(1);
        result.Add(row);
    }
    return result;
}

// Original approach, modified to use list capacities:
public static IList<IList<int>> Generate_Capacity(int numRows)
{
    IList<IList<int>> result = new List<IList<int>>(numRows);
    if (numRows == 0)
    {
        return result;
    }
    List<int> row = new List<int>(1);
    row.Add(1);
    result.Add(row);
    if (numRows == 1)
    {
        return result;
    }

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        row = new List<int>(i + 1);
        row.Add(1);
        for (int j = 0; j < prevRow.Count - 1; j++)
        {
            row.Add(prevRow[j] + prevRow[j + 1]);
        }
        row.Add(1);
        result.Add(row);
    }
    return result;
}

// Original approach, modified to use list capacities and caching the previous row's left value:
public static IList<IList<int>> Generate_Capacity_Improved(int numRows)
{
    IList<IList<int>> result = new List<IList<int>>(numRows);
    if (numRows == 0)
    {
        return result;
    }
    List<int> row = new List<int>(1);
    row.Add(1);
    result.Add(row);
    if (numRows == 1)
    {
        return result;
    }

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        row = new List<int>(i + 1);
        var left = 0;
        for (int j = 0; j < prevRow.Count; j++)
        {
            int right = prevRow[j];
            row.Add(left + right);
            left = right;
        }
        row.Add(1);
        result.Add(row);
    }
    return result;
}

// Using arrays instead of lists:
public static IList<IList<int>> Generate_Array(int numRows)
{
    var result = new int[numRows][];
    if (numRows == 0)
        return result;

    result[0] = new int[] { 1 };
    if (numRows == 1)
        return result;

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        var row = new int[i + 1];
        row[0] = 1;
        for (int j = 0; j < i - 1; j++)
            row[j + 1] = prevRow[j] + prevRow[j + 1];
        row[i] = 1;
        result[i] = row;
    }
    return result;
}

// Using arrays instead of lists, and caching the previous row's left value:
public static IList<IList<int>> Generate_Array_Improved(int numRows)
{
    var result = new int[numRows][];
    if (numRows == 0)
        return result;

    result[0] = new int[] { 1 };
    if (numRows == 1)
        return result;

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        var row = new int[i + 1];

        var left = 0;
        for (int j = 0; j < i; j++)
        {
            int right = prevRow[j];
            row[j] = left + right;
            left = right;
        }
        row[i] = 1;
        result[i] = row;
    }
    return result;
}

// Using arrays instead of lists, caching the previous row's left value, and using row reflection:
public static IList<IList<int>> Generate_Array_Improved_Reflective(int numRows)
{
    var result = new int[numRows][];
    if (numRows == 0)
        return result;

    result[0] = new int[] { 1 };
    if (numRows == 1)
        return result;

    for (int i = 1; i < numRows; i++)
    {
        var prevRow = result[i - 1];
        var row = new int[i + 1];

        var left = 0;
        var mid = (i / 2) + 1;
        for (int j = 0; j < mid; j++)
        {
            int right = prevRow[j];
            var sum = left + right;
            row[j] = sum;
            row[i - j] = sum;
            left = right;
        }
        result[i] = row;
    }
    return result;
}

// Using arrays, calculating each row individually:
public static IList<IList<int>> Generate_PerRow(int numRows)
{
    var result = new int[numRows][];
    for (int i = 0; i < numRows; i++)
    {
        var row = new int[i + 1];
        row[0] = 1;
        for (int j = 0; j < i; j++)
            row[j + 1] = row[j] * (i - j) / (j + 1);
        result[i] = row;
    }
    return result;
}

// Using arrays, calculating each row individually, using row reflection:
public static IList<IList<int>> Generate_PerRow_Reflective(int numRows)
{
    var result = new int[numRows][];
    for (int i = 0; i < numRows; i++)
    {
        var row = new int[i + 1];
        row[0] = 1;
        row[i] = 1;
        var mid = i / 2;
        for (int j = 0; j < mid; j++)
        {
            var value = row[j] * (i - j) / (j + 1);
            row[j + 1] = value;
            row[i - j - 1] = value;
        }
        result[i] = row;
    }
    return result;
}

Answer 4

After my initial disappointment with the performance of the previous implementation below, I got to thinking. Now that we have a generator function why do allocation at all?

The other good answers allocate memory to the triangle as a necessity, this enables back referencing to calculate future values. If you have a generator function, you don't need to back reference the triangle and therefore it is no longer necessary to store the previous values to calculate the next (except for the one, immediately previous in the row.)

When it comes to performance, the allocation of bytes becomes quite expensive. If you don't need to access values out of sequence this approach avoids the allocation overhead. Further note, that any given row can be generated by calling the Row function directly.

public static class JodrellMk2Pascal
{
    public static IEnumerable<IEnumerable<int>> Triangle(int n)
    {
        for (var i = 0; i < n; i++)
        {
            yield return Row(i);
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static IEnumerable<int> Row(int n)
    {
        var last = 1;
        yield return last;

        for (var k = 0; k < n; k++)
        {
            yield return last = last * (n - k) / (k + 1);
        }
    }
}

---

If performance is your goal you'd be better off with an identity function and better memory management.

The additional benefit here, is that you can jump to the 53rd line Line(52) without having to calculate the preceding triangle.

public static class Pascal
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ReadOnlySpan<long[]> Triangle(int n)
    {
        if (n < 1)
        {
            return ReadOnlySpan<long[]>.Empty;
        }

        Span<long[]> triangle = new long[n][];

        for (var r = 0; r < n; r++)
        {
            triangle[r] = Line(r).ToArray();
        }

        return triangle;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ReadOnlySpan<long> Line(int n)
    {
        if (n < 0)
        {
            return ReadOnlySpan<long>.Empty;
        }

        if (n == 0)
        {
            return (ReadOnlySpan<long>)new long[]
            {
                1L
            };
        }

        Span<long> result = new long[n + 1];

        result[0] = 1L;
        for (var k = 0; k < n; k++)
        {
            result[k + 1] = result[k] * (n - k) / (k + 1);
        }

        return result;
    }
}

Answer 5

You use lists, which are great when you have a flexible number of elements in it and you might add/remove some, but in your case, you know exactly how many elements each list would contain and there is no possibility for it to change. In this case, you are using the wrong data structure because the list has unnecessary overhead. You need an array or arrays. The creation logic looks like this :

int[][] rows = new int[n][];
for (i = 0; i < n; i++)
{
    rows[i] = new int[i + 1];
}

This way, you already have your structure created, all you need to do is fill it. The other advantage is that you take exactly the amount of memory you're supposed to use, so you don't have any overhead.

You also know that every first and last element of a row is one, so why not do this at the same time?

int[][] rows = new int[n][];
for (i = 0; i < n; i++)
{
    rows[i] = new int[i + 1];
    rows[i][0] = 1;

    // This is an unnecessary operation for i = 0, but that's a very small problem.
    rows[i][rows[i].Length - 1] = 1;
}

Now what's left is to fill the arrays and your code already does it pretty well, but now we're using arrays instead of lists so we can't use Add.

int[][] rows = new int[n][];
for (int i = 0; i < n; i++)
{
    rows[i] = new int[i + 1];
    rows[i][0] = 1;

    // This is an unnecessary operation for i = 0, but that's a very small problem.
    rows[i][rows[i].Length - 1] = 1;

    if (i > 1)
    {
        // Notice that we start at 1 instead of zero and end one index before the end to preserve
        // the 1s that we added earlier.
        for (int j = 1; j < rows[i].Length - 1; j++)
        {
            var previousRow = rows[i - 1];

            rows[i][j] = previousRow[j - 1] + previousRow[j];
        }
    }
}

The code above is pretty much the same as yours, but with arrays instead of lists.

With this code, you also don't need to check for n == 1, the check will be made in the for loop where you wouldn't enter if n == 1. Using my version of the code, you also don't need to check for n == 0, because it will return an empty int[][] anyways.

Benchmarking

I've used BenchmarkDotNet to test both our solutions.

The end result is (I wanted to add a table but I don't know if it's possible) :

My method : 2.545us (mean time) +- 0.0504us (std)

Your method : 20.766us (mean time) +- 0.4133us (err)

The benchmark code is the following :

[RPlotExporter, RankColumn]
public class PascalTriangle
{
    //The MyCode method is the code written above.
    [Benchmark]
    public int[][] myCode() => MyCode(33);

    //The YourCode method is literally your post.
    [Benchmark]
    public IList<IList<int>> yourCode() => yourCode(33);
}

class Program
{
    static void Main(string[] args)
    {
        var summary = BenchmarkRunner.Run<PascalTriangle>();
        Console.ReadKey();
    }
}

Answer 6

Types

The code uses Int. The largest Int in C# is ~2e9. This means that once a row has two cells each greater than 1e9, there will be an overflow. Even though using uint only means the code can calculate one more row prior to overflow, there's no reason to use a signed value. Using long puts overflow much further into the computation and ulong would again probably give us one more row than long. BigInteger takes overflow off the table.

Memory

The memory of footprint of the proposed code is an area where performance can be improved. Without considering possible compiler optimization, it allocates O(n²) memory locations (n rows averaging n/2 length).

Hardening

Robustness could be improved by a streaming results as they are calculated. Consider the case:

PascalTriangle.Generate(int64.MaxValue);  //9,223,372,036,854,775,807

The proposed code will probably OutOfMemoryException without producing any work. It's not that a streaming solution will necessarily complete the task. But if we stream, we might have the last row before it crashed and that's enough to restart from where we were instead of being back at triangle one.

The memory footprint of a streaming solution is O(n). We can quickly calculate row r_i+1 by retaining row r_i. The maximum memory to calculate a row when streaming is 2n-1 memory locations.

Protocols

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

Looks a lot like a protocol. The proposed code does not return the data in the format of its specification. It returns a C# object, instead. There's no basis to assume that the consuming code is under our control or even relies on .NET.

Of course we have to assume something about the consuming code. Outputting a stream of bytes is traditionally a very low denominator for API's. The output can be encoded as ASCII characters. The example output (without whitespace) becomes:

91 91 49 93 44 91 49 44 49 93 44 91 49 44 50 44 49 93 44 91 49 44 51 44 51 44 49 93 44 91 49 44 52 44 54 44 52 44 49 93 93 

Bandwidth

The streamed ASCII is 41 bytes. Naively, the proposed code uses 60 bytes (15 four byte integers). If ulongs were used the ASCII would tend to be more space efficient until the cell values in the Triange approached 10e6 (six ascii digits and a ,) and approximately as efficient until cell values approached 10e7 (seven ascii digits and a ,).

A custom binary encoding would allow two characters per byte. We only need to encode 14 characters: EOF,0-9,[,], and ,. We still have bits left in our nibble to include the space and newline characters and stream formatted output that matches the example.

Leetcode

The Leetcode problem looks a lot like Fizzbuzz. But unlike Fizzbuzz, the Leetcode problem isn't bounded from one to one hundred. The considerations I've listed in this review would be inappropriate to Fizzbuzz solutions. Fizzbuzz doens't have any unknown conditions. Fizzbuzz can't be fuzzed.

Leetcode questions have unknowns. They can be fuzzed. They scale beyond 'one to one hundred'. That's what makes them useful starting points for engineering analysis. Unlike Fizzbuzz, they can be used to answer important questions in addition to "can the person write a loop and do they know the modulo operator?". Leetcode solutions that look like Fizzbuzz solutions are at the low end of solution quality.

Remarks

• It's good that within limits the proposed code works.
• A more thorough test suite would be a starting point to increase it's robustness.
• Because the code returns an .NET object, it is not clear that the code meets the specification.
• Documentation is absent. Even comments
• The code embodies assumptions about the input that may be unwarranted.

Laziness

Because the stream abstraction entails the idea of a consumer, a program using streams only needs to produce values as quickly as the consumer consumes them. The memory footprint can be reduced further by lazily calculating each value.

Cell i in row j can be computed directly on an as needed basis using factorials. Factorials are slower (more computationally intensive) than simple addition. It's a tradeoff. That's engineering.

Answer 7

Just a small remark: your entire code is in a namespace called RecurssionQuestions [sic], but it is not recursive. That is confusing.

Answer 8

Musing on this question some more, it occurred to me that Pascals Triangle is of course completely constant and that generating the triangle more than once is in fact an overhead.

Whatever function is used to generate the triangle, caching common values would save allocation and clock cycles.

Something like this would help,

private static readonly int[] Row0 = { 1 };
private static readonly int[] Row1 = { 1, 1 };
private static readonly int[] Row2 = { 1, 2, 1 };
private static readonly int[] Row3 = { 1, 3, 3, 1 };
private static readonly int[] Row4 = { 1, 4, 6, 4, 1 };
private static readonly int[] Row5 = { 1, 5, 10, 10, 5, 1 };
private static readonly int[] Row6 = { 1, 6, 15, 20, 15, 6, 1 };
private static readonly int[] Row7 = { 1, 7, 21, 35, 35, 21, 7, 1 };
private static readonly int[] Row8 = { 1, 8, 28, 56, 70, 56, 28, 8, 1 };
private static readonly int[] Row9 = { 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 };

private static int[][] Triangle(byte n) =>
    n switch
    {
        0 => new[] { Row0 },
        1 => new[] { Row0, Row1 },
        2 => new[] { Row0, Row1, Row2 },
        3 => new[] { Row0, Row1, Row2, Row3 },
        4 => new[] { Row0, Row1, Row2, Row3, Row4 },
        5 => new[] { Row0, Row1, Row2, Row3, Row4, Row5 },
        6 => new[] { Row0, Row1, Row2, Row3, Row4, Row5, Row6 },
        7 => new[] { Row0, Row1, Row2, Row3, Row4, Row5, Row6, Row7 },
        8 => new[] { Row0, Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8 },
        9 => new[] { Row0, Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9 },
        _ => throw new ArgumentOutOfRangeException(nameof(n))
    };