Best way to generate Pascal Triangle

Question

I am using the concept of level order traversal to generate Pascal Triangle.

Here is the code snippet:

void printPascalTriangle(int n)
{
    int line=1,Q[50]={0},f=-1,r=-1,prev,t;

    Enqueue(Q,&f,&r,1);
    Enqueue(Q,&f,&r,0);

    prev=0;
    while(line!=n)
    {
            t = Dequeue(Q,&f,&r);

            if( !t )
            {
                    line++;
                    prev = 0;
                    Enqueue(Q,&f,&r,1);

                    if(!isEmpty(&r))
                            Enqueue(Q,&f,&r,0);

                    printf("\n");
            }
            else
            {
                    printf("%d ", t);
                    Enqueue(Q,&f,&r,prev+t);
                    prev = t;
            }
    }
}

The complete code is here:

The advantage with this approach is that its space complexity is O(N) where N is the number of lines.

Is there any better way of doing the same?

Answer 1

Since your only concern is space-complexity, and you're using int (as opposed to some sort of big-integer type of potentially unbounded size), you can actually achieve space complexity of O(1) by using these two facts:

• C(n, 0) = 1 for 0 ≤ n
• C(n, k+1) = C(n, k) × (n − k) / (k + 1) for 0 ≤ k < n

These two facts mean that you can compute each element using only the previous element of the same row, so you never have to save more than one element at a time.

(By C(n, k) I mean the element in row n, position k of Pascal's triangle, assuming that rows and positions are numbered starting from 0.)

Answer 2

I take it you wanted code, not an equation? Here are two JavaScript implementations, one with factorial calculation and one without it. I'm undecided on which one I prefer:

//1. non-factorial option
function GenerateTriangle1(rows) {
    var pascalsTriangle = [];

    for (var r = 0; r < rows; r++) {
        var elements = r + 1;
        var level = [];

        for (var i = 0; i < elements; i++) {
            if (i === 0 || i === elements - 1 || r === 1)
                level[i] = 1;
            else {
                var prevRow = pascalsTriangle[r - 1];
                level[i] = prevRow[i - 1] + prevRow[i];
            }
        }

        pascalsTriangle[r] = level;
    }

    return pascalsTriangle;
}

//2. Factorial option
function GenerateTriangle2(rows) {
    var pascalsTriangle = [];

    for (var r = 0; r < rows; r++) {
        var elements = r + 1;
        var level = [];

        for (var i = 0; i < elements; i++) {
            level[i] = CalculateTerm(r, i);
        }

        pascalsTriangle[r] = level;
    }

    return pascalsTriangle;
}

function CalculateTerm(row, term) {
    var divisor = Factorial(term) * Factorial(row - term);
    return divisor > 0 ? Factorial(row) / divisor : 1;
}

function Factorial(n) {
    return n > 1 ? n * Factorial(n - 1) : n;
}

console.log(GenerateTriangle1(4))
console.log(GenerateTriangle1(5))