# 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]
]


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

{
/// <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, 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>();
if (numRows == 1)
{
return result;
}

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

• To calculate the n th row, you need the n-1 th row to be calculated. This means your algorithm can only calculate top-down, and can not be extended to calculate a section or a single row. You might want to read about it here: en.wikipedia.org/wiki/…. Aug 21, 2019 at 5:04

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];
left = right;
}


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.

• I am not sure whether we could gain performance for the bigger rows with this, but since each row is reflective around its centre, perhaps we should only calculate half the row and reflect the other half .. planetmath.org/… Aug 21, 2019 at 5:07
• +1. Some quick testing shows that using a list's capacity can make things 20-50% faster (less gain for higher numbers of rows), whereas using arrays directly is consistently more than 80% faster. Caching the previous row's left value is about 10-20% faster, and making use of the reflective nature of rows can yield another 10% improvement. Aug 21, 2019 at 7:46
• @PieterWitvoet would you mind sharing your benchmark code? (since you've bothered to test it, that would be worthy of an answer in my book). I'm most surprised by the array performance: I didn't expect that much overhead from List<T> (or was that IList<T>?) Aug 21, 2019 at 8:42
• @VisualMelon: sure, here you go. Aug 21, 2019 at 9:47

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
{
}
}


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.

• +1 I probably should have though about this before even mentioning memory... Aug 21, 2019 at 9:01
• @VisualMelon thanks, it actually surprised me how quickly the values grew. The maximum for each row nearly doubles.
Aug 21, 2019 at 13:44
• @JAD From the binomial theorem, when $n$ is even the biggest term is n! / [(n/2)! (n/2)!], and using Stirling's approximation for factorials, that is the same order as 2^n. That is almost obvious, because when you have a row with two equal "biggest terms", the biggest term in the next row is the sum of two the equal numbers, i.e. twice as big. Aug 21, 2019 at 23:38
• @alephzero yeah, when I thought about it more carefully, it made sense :) Each term grows by a factor n / ceil(n/2), which is 2 when n is even, and approaches 2 as n grows.
Aug 22, 2019 at 5:31

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>();
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];
left = right;
}
}
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);
if (numRows == 1)
{
return result;
}

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

• I wonder how much of the benefit from arrays is because it doesn't indirect through IList; does swapping IList<IList<int>> result = new List<IList<int>>(); for var result = new List<IList<int>>(); make any difference? Aug 21, 2019 at 9:50
• @VisualMelon: good point. IList<IList<int>> result is twice as slow compared to int[][] result. Aug 21, 2019 at 9:57

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)]
{
if (n < 1)
{
}

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

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

return triangle;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
{
if (n < 0)
{
}

if (n == 0)
{
{
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;
}
}

• I don't understand the use of ReadOnlySpan: I think it will only add overhead. A quick benchmark (for n=10, on my machine, etc.) sees a version which just works with long[] running in about 80% of the time. The computing of the row independently also seems to be slower in practise according to Peter (I don't see a consistent advantage on my machine), but his implementation seems to be about twice as fast as your implementation (which I figure will be down to his exploiting symmetry and not performing the result[k] lookup). Aug 21, 2019 at 15:44
• @VisualMelon, interesting, are you using github.com/dotnet/BenchmarkDotNet? There is obviously a hit to using long, re: memory allocation. Aug 21, 2019 at 15:51
• New data: gist.github.com/VisualMelon/… Aug 21, 2019 at 16:08
• Nice to see someone implement the lazy version properly, but you should probably add some explanation of why you might want to do this (code alone doesn't make for a very good review). Aug 22, 2019 at 13:11
• @VisualMelon advice taken. Aug 22, 2019 at 13:29

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>();
}
}

• Comments are not for extended discussion; this conversation has been moved to chat. Aug 21, 2019 at 16:59

## 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(n2) 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 ri+1 by retaining row ri. 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.

• The largest signed 32-bit integer is $2^{31} - 1 \approx 2 \times 10^9$. You've got an out-by-one error in the exponent. Aug 22, 2019 at 13:36
• @PeterTaylor Thanks, I made the edit. Aug 22, 2019 at 17:10

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

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))
};

• Lazy people let the code generate the data :-P I would never write anything like this when I can create a function to do it for me. In fact, I find this is a terrible suggestion :-\ You're wasted when I tell you to add three more rows. I'd even say this is an anti-suggestion. It makes the code worse, not better. Aug 29, 2019 at 9:11
• This would make sense if (1) you've done some market research and came to the conclusion most consumers would require a solution for n <= 9 (2) you have, of course, generated the rows with a template like t4 (3) you'd povide a public entry point that would not throw the exception above, but calculates in place for n > 9 Aug 29, 2019 at 11:05
• @dfhwze, larger triangles require the earlier rows, so they could be reused, extrapolating further, you could apply caching for generated data too. Aug 30, 2019 at 8:54
• @t3chb0t My original answer implemented a very concise generator but, if performance is your goal, like in the question, than its better to do all you can to optimise performance; even if it costs some elegance and maintenance. Aug 30, 2019 at 9:04