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:

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 

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