Making Pascal's Triangle: LeetCode's Challenge & Code Solution

#leetcode #algorithms #typescript

Problem:
I was wandering Leetcode (like usual) when I came the 118th problem, Pascal's Triangle, creating a Pascal's Triangle only from a single input, the triangle's height.

The code

function generate(numRows: number): number[][] {
  let pascalsTriangle: number[][] = new Array();

  for (let i = 0; i < numRows; i++) {
    let row: number[] = [];

    for (let j = 0; j < i + 1; j++) {
      row.push(fac(i) / (fac(j) * fac(i - j)));
    }

    pascalsTrianglet.push(row);
  }

  return pascalsTriangle;
}

function fac(n: number): number {
  if (n < 0) return -1;
  else if (n == 0) return 1;
  else {
    return n * fac(n - 1);
  }
}

Thought Process:
The first thing I wanted to know was how could I create a Pascal's Triangle without code.

Turns out, that's actually pretty easy, thanks to MathIsFun.com (go check them out!) I could find exactally what I needed to learn all about Pascal's Triangles

I was able to find the formula and a pretty cool illustration to show the logic behind the formula:

TL;DR: Divide column's factorial by (row's factorial * (column - row)'s factorial)

Altough this formula only get's us one row, we can dynamically change the variables using code, so that's exactally what we're doing!

Code Breakdown:

The main function

function generate(numRows: number): number[][] {
  let pascalsTriangle: number[][] = new Array();

  for (let i = 0; i < numRows; i++) {
    let row: number[] = [];

    for (let j = 0; j < i + 1; j++) {
      row.push(fac(i) / (fac(j) * fac(i - j)));
    }

    pascalsTriangle.push(row);
  }

  return pascalsTriangle;
}

In the code above we start out by creating a 2d array and initializing a for loop for each row of the triangle

let pascalsTriangle: number[][] = new Array();

for (let i = 0; i < numRows; i++) {
  let row: number[] = [];

  for (let j = 0; j < i + 1; j++) {
    row.push(fac(i) / (fac(j) * fac(i - j)));
  }

  pascalsTriangle.push(row);
}

In this first loop, we run another loop for calculating the triangle's i'th row

for (let j = 0; j < i + 1; j++) {
  row.push(fac(i) / (fac(j) * fac(i - j)));
}

Since we dont have a factorial function in JS, we need to write our own!

function fac(n: number): number {
  if (n < 0) return -1;
  else if (n == 0) return 1;
  else {
    return n * fac(n - 1);
  }
}

Finally, we append the row to our triangle and return the pascalsTriangle variable after the first loop

    pascalsTriangle.push(row);
  }

  return pascalsTriangle;
}

And that's it!

It's definitely not the best or most efficient solution, but I had a lot of fun researching about the topic and learning something new, and I hope you could enjoy this little article!