The Algorithms logo
The Algorithms
AboutDonate

Pascals Triangle

O
/**
 * Pascal's Triangle is an array of binomial coefficients. It can be used for unwrapping terms like
 * (a + b)^5.
 * To construct Pascal's Triangle you add the numbers above the child entry together. Here are the first five rows:
 *     1
 *    1 1
 *   1 2 1
 *  1 3 3 1
 * 1 4 6 4 1
 *
 * Time Complexity: quadratic (O(n^2)).
 *
 * @param n The exponent / The index of the searched row.
 * @returns The nth row of Pascal's Triangle
 * @see https://en.wikipedia.org/wiki/Pascal's_triangle
 */
export const pascalsTriangle = (n: number): number[] => {
  let arr: number[][] = [];
  for (let i: number = 0; i < n; i++) {
    if (i === 0) {
      arr.push([1]);
      continue;
    }

    let lastRow: number[] = arr[i - 1];
    let temp: number[] = [];
    for (let j: number = 0; j < lastRow.length + 1; j++) {
      if (j === 0 || j === lastRow.length) {
        temp.push(1);
        continue;
      }

      temp.push(lastRow[j - 1] + lastRow[j]);
    }

    arr.push(temp);
  }

  return arr[arr.length - 1];
};