C++ and Python to Compute the Pascal Triangle

Given an index k, return the k-th row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].
Could you optimize your algorithm to use only O(k) extra space?

C++ O(n^2) to Compute the Pascal Triangle

It is easy to know that each number in the triangle equals to the sum of the two numbers of its shoulder if there are any.

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> r;
        if (rowIndex == 0) {
            r.push_back(1);
            return r;
        }
        r.resize(rowIndex + 1);
        r[0] = 1;
        r[1] = 1;
        for (int i = 0; i < rowIndex - 1; i ++) {
            for (int j = rowIndex; j > 0; j --) {
                r[j] += r[j - 1];
            }
        }
        return r;
    }
};

We don’t need to store two dimension pascal triangles as when we calculate the k-th row all we need is (k-1)-th row of numbers. We allocate rowIndex + 1 elements in the vector and set the first two elements to both ones. rowIndex = 0 is the special case so we need to return a vector that contains a single element 1 and return it.

Then for next rowIndex – 1 iterations, we sum from right to the left interactively. The C++ submission is fast.

c-plus-plus-pascal-triangle

The Python equivalence looks simpler:

class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]
        r = [0] * (rowIndex + 1)
        r[0] = 1
        r[1] = 1
        for i in range(rowIndex - 1):
            for j in range(rowIndex, 0, -1):
                r[j] = r[j] + r[j - 1]
        return r

But python is generally slower in terms of performance.

python-submission

Compute the Pacal Triangle in C++ O(n) time O(k) space

Each line of Pascal’s Triangle is a full set of Combination number based on k .

comb(k,p) = k! /( p! *(k-p)!) = comb(k,k-p)

if p < k-p

comb(k,p) = comb(k,p-1) * (k-p+1) / p

Because :

comb(k,p) = [ k * (k-1) * (k-2) *... (k-p+1)] / [1 * 2 * 3 *...(p)]

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 1);
        int small = rowIndex / 2;
        long comb = 1;
        int j = 1;
        for (int i = rowIndex; i >= small; i--){
            comb *= i;
            comb /= j;
            j ++;
            ans[i-1] = (int)comb;
            ans[j-1] = (int)comb;
        }
        return ans;
    }
};

This runs approximately two times faster (2ms) than the above O(n^2) solution. A similar solution gives also 2ms (calculate the first half of the array)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex + 1, 1);
        long current_multiplier = 1;
        for (int n = 1; n <= rowIndex / 2; ++n) {
            current_multiplier *= (rowIndex - n + 1);
            current_multiplier /= n;
            result[n] = current_multiplier;
        }
        for (int n = rowIndex / 2 + 1; n < rowIndex; ++n) {
            result[n] = result[rowIndex - n];
        }
        return result;
    }
};

To compute the N-th row of a Pascal Triangle: You can use Dynamic Programming algorithm: Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm

Pascal Triangle Implementations:

• Teaching Kids Programming – Pascal Triangle Algorithms and Applications
• Coding Exercise – Pascal Triangle II – C++ and Python Solution
• How to Print Pascal Triangle in C++ (with Source Code)
• Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm
• GoLang: Generate a Pascal Triangle

–EOF (The Ultimate Computing & Technology Blog) —