0
\$\begingroup\$

I have been given an exam to implement Pascal Triangle in JavaScript, I have seen that it somehow similar on fibonacci sequence. With that I have come up with the solution below.

function pascalTriangle(n){
  var data = [[1],[1,1]];
  var rowNum = n - 2;
  for (var i = 1; i <= rowNum; i++){
  	var curr = i;
    data.push([1]);
    for (var x = 0; x< data[curr].length - 1; x++){
      var calcMid = data[curr][x] + data[curr][x + 1];
      data[curr+1].push(calcMid);
    }
    data[curr+1].push(1);
  }
  console.log(data);
}
pascalTriangle(5);

What I did is that I first initialize the 1st and 2nd row of the Pascal Triangle and then do the calculation for the middle with the idea from fibonacci sequence.

I feel that the solution the I have come up can be improved.

\$\endgroup\$
2
\$\begingroup\$

Minor style points and an alternative solution.

With these types of problems the first port of call is always Wikipedia to get as much info as you can before you start on creating a solution.

Two things stand out about the solution.

  1. The rows are symmetrical, the right side is a mirror of the left.
  2. There is a formula that lets you calculate a row which can help reduce the complexity.

Your code

There is nothing majorly wrong with the code, the following are just general style points

  • Do the output outside the function.
  • Use const for variables that do not change.
  • Declare variables with var at the top of the function or use let to declare variables in the block they are to be used.
  • In nested loops try to avoid double indexing by creating a reference to the inner array outside the inner loops.
  • The function is not complete, as it does not return the correct results for pascalTriangle(0) and pascalTriangle(1) a simple if statement can take care of that.
  • Don't duplicate variables for no reason. The variable i (out loop iteration counter) is immediately copied to a variable curr and neither are changed inside the loop.
  • When writing we put a space after a comma, this make it easier to read then without,thus illustrated. The same with code, put spaces after commas so that it does not all blend together. Same for operators where the convention is a space either side. eg data[curr+1] should be data[curr + 1] and data = [[1],[1,1]]; should be data = [[1], [1, 1]];

  • (minor point as the problem is simple and solution sort) You could use some better names for some of the variables.

Rewrite

Rewriting your function using the above points.

function pascalTriangle1(rowCount) {
    if (rowCount === 0) { return [] }
    if (rowCount === 1) { return [[1]] }
    const rows = [[1], [1, 1]];
    var prevRow = rows[1];
    for (let n = 1; n < rowCount - 1; n += 1) {
        const row = [1];
        let val = prevRow[0];
        for (let k = 0; k < prevRow.length - 1; k += 1) {
            row.push(val + (val = prevRow[k + 1]));
        }
        row.push(1);
        rows.push(row);
        prevRow = row;
    }
    return rows;
}

Alternative solution

The following reduces the number of calculations to about half by exploiting the symmetry of each row.

Further improvements can be made by using Float64Array and pre-calculating the triangle size, then indexing directly into the array, avoiding the expensive array creation left and right and concatenation for each row. But that would only show any real benefit for very large triangles, where he need to hold all the rows would be questionable.

const pascalTriangle = rowCount => {
    const createRow = rowIndex => {
        var k = 1, val = 1;
        const n = rowIndex + 1;
        const left = [val];
        const right = [val];
        while (k < n / 2) {  // only do half the row
            val = val * (n - k) / k++;
            left.push(val);
            right.unshift(val);
        }
        if (n % 2) { right.shift() }  // when n is odd remove first right item
        return [...left, ...right];
    }
    const rows = [];
    if (rowCount > 0) {
        let i = 1;
        rows.push([1]);
        while (i < rowCount) {  rows.push(createRow(i++)) }
    }
    return rows;
}
\$\endgroup\$
  • \$\begingroup\$ Cool. Thanks a lot. I will keep that in mind the style points that you have shared. \$\endgroup\$ – davecar21 Apr 5 '18 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.