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