DEV Community

Cover image for C# LeetCode 118: Pascal's Triangle - (Easy)
Grant Riordan
Grant Riordan

Posted on

C# LeetCode 118: Pascal's Triangle - (Easy)

Problem

Given an integer numRows, return the first numRows of Pascal's triangle.

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

pascals triangle example

Approach

Ok, so we've probably all done a puzzle like this before on a test, or puzzle book on holiday. The sum of the previous diagonal numbers form the current number.

Where to start?

  • Well firstly we know that all the edges of the rows need to equal 1 so thats one thing,

  • We will need to loop over all the rows + columns, adding up the diagonals as we go.

How It Works

Outer Loop (Rows)
We generate each row from i = 0 to numRows - 1.
Row length = i + 1

Edges Are Always 1

row[0] = 1
row[i] = 1
Enter fullscreen mode Exit fullscreen mode

Inner Loop (Filling Middle Elements)
Because we know the first element is 1 we can start our columns at index of 1 (block 2)

row[j] = sum of the two numbers above it

This uses the previous row stored in result[i - 1].

Code

public IList<IList<int>> Generate(int numRows)
{
    var result = new List<IList<int>>();
    var current = 1;


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

        for (var j = 1; j < i; j++)
        {
            row[j] = result[i - 1][j - 1] + result[i - 1][j];
        }

        result.Add(row);
    }

    return result;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)