LeetCode - Pascal's Triangle | Darren's Blog

Given numRows, generate the first numRows of Pascal's triangle.

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Each list p is generated by its previous list q . Except for the first and the last element,p[i]=q[i−1]+q[i]

public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows == 0)

            return result;

        // Generate the first list

        List<Integer> previous = new ArrayList<Integer>(1);

        previous.add(1);

        result.add(previous);

        // A new list is generated base on its previous list

        for (int i = 2; i <= numRows; i++) {

            List<Integer> current = new ArrayList<Integer>(i);

            current.add(1);

            for (int j = 1; j < previous.size(); j++)

                current.add(previous.get(j-1) + previous.get(j));

            current.add(1);

            result.add(current);

            previous = current;

        }

        return result;

    }

http://www.geeksforgeeks.org/pascal-triangle/

Method 1 ( O(n^3) time complexity )

Every entry in a line is value of a Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.

C(line, i)   = line! / ( (line-i)! * i! ) 

void printPascal(int n)

{

  // Iterate through every line and print entries in it

  for (int line = 0; line < n; line++)

  {

    // Every line has number of integers equal to line number

    for (int i = 0; i <= line; i++)

      printf("%d ", binomialCoeff(line, i));

    printf("\n");

  }

}

// See http://www.geeksforgeeks.org/archives/25621 for details of this function

int binomialCoeff(int n, int k)

{

    int res = 1;

    if (k > n - k)

       k = n - k;

    for (int i = 0; i < k; ++i)

    {

        res *= (n - i);

        res /= (i + 1);

    }

    return res;

}

Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.

void printPascal(int n)

{

  int arr[n][n]; // An auxiliary array to store generated pscal triangle values

  // Iterate through every line and print integer(s) in it

  for (int line = 0; line < n; line++)

  {

    // Every line has number of integers equal to line number

    for (int i = 0; i <= line; i++)

    {

      // First and last values in every row are 1

      if (line == i || i == 0)

           arr[line][i] = 1;

      else // Other values are sum of values just above and left of above

           arr[line][i] = arr[line-1][i-1] + arr[line-1][i];

      printf("%d ", arr[line][i]);

    }

    printf("\n");

  }

}

Method 3 ( O(n^2) time and O(1) extra space )

This method is based on method 1. We know that ith entry in a line number line is Binomial CoefficientC(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line - i + 1) / i

void printPascal(int n)

{

  for (int line = 1; line <= n; line++)

  {

    int C = 1;  // used to represent C(line, i)

    for (int i = 1; i <= line; i++)  

    {

      printf("%d ", C);  // The first value in a line is always 1

      C = C * (line - i) / i;  

    }

    printf("\n");

  }

}

Dynamic Programming | Set 9 (Binomial Coefficient)

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

http://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) * 
                                    ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)  // we can change r to n-r if r > n-r 

Read full article from LeetCode - Pascal's Triangle | Darren's Blog