Skip to content
DSA in JavaScript
Array & String Classics

Pascal's Triangle

Algorithm · Core

Level: CoreGreedy

Step through it: Greedy pattern

jump
2↑ start
3
1
1
4

Step 1 of 5

Goal: can you reach the last cell if each number is the farthest you may jump from that cell? Idea: only track the farthest cell you could possibly reach so far. Never try individual routes.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients.

The rows of Pascal's triangle are conventionally enumerated starting with row n = 0 at the top (the 0th row). The entries in each row are numbered from the left beginning with k = 0 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0 (the topmost row), there is a unique nonzero entry 1. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the initial number in the first (or any other) row is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.

Formula

The entry in the nth row and kth column of Pascal's triangle is denoted . For example, the unique nonzero entry in the topmost row is .

With this notation, the construction of the previous paragraph may be written as follows:

for any non-negative integer n and any integer k between 0 and n, inclusive.

Calculating triangle entries in O(n) time

We know that i-th entry in a line number lineNumber is Binomial Coefficient C(lineNumber, i) and all lines start with value 1. The idea is to calculate C(lineNumber, i) using C(lineNumber, i-1). It can be calculated in O(1) time using the following:

C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!)
C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)

We can derive following expression from above two expressions:

C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i

So C(lineNumber, i) can be calculated from C(lineNumber, i - 1) in O(1) time.

Code

pascalTriangle.js
/**
 * @param {number} lineNumber - zero based.
 * @return {number[]}
 */
export default function pascalTriangle(lineNumber) {
  const currentLine = [1];

  const currentLineSize = lineNumber + 1;

  for (let numIndex = 1; numIndex < currentLineSize; numIndex += 1) {
    // See explanation of this formula in README.
    currentLine[numIndex] = (currentLine[numIndex - 1] * (lineNumber - numIndex + 1)) / numIndex;
  }

  return currentLine;
}
pascalTriangleRecursive.js
/**
 * @param {number} lineNumber - zero based.
 * @return {number[]}
 */
export default function pascalTriangleRecursive(lineNumber) {
  if (lineNumber === 0) {
    return [1];
  }

  const currentLineSize = lineNumber + 1;
  const previousLineSize = currentLineSize - 1;

  // Create container for current line values.
  const currentLine = [];

  // We'll calculate current line based on previous one.
  const previousLine = pascalTriangleRecursive(lineNumber - 1);

  // Let's go through all elements of current line except the first and
  // last one (since they were and will be filled with 1's) and calculate
  // current coefficient based on previous line.
  for (let numIndex = 0; numIndex < currentLineSize; numIndex += 1) {
    const leftCoefficient = (numIndex - 1) >= 0 ? previousLine[numIndex - 1] : 0;
    const rightCoefficient = numIndex < previousLineSize ? previousLine[numIndex] : 0;

    currentLine[numIndex] = leftCoefficient + rightCoefficient;
  }

  return currentLine;
}

References

Practice

Spotted a mistake or something unclear? Report it on GitHub.

Square Matrix In-Place Rotation

Algorithm · Core

Factorial

Algorithm · Starter

On this page

FormulaCalculating triangle entries in O(n) timeCodeReferences