Pascal’s Triangle

Pascal’s triangle is a problem where you want to print a triangle of a certain height where each element is the sum of the 2 elements above it.  The first row is 1, the second row is 2 1’s, and then the pattern builds from there with 1 on the ends and the other elements being the sum of their parents.

For Example:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

Generalized Solution

It’s always good to (first) try to solve algorithms yourself without looking at other peoples’ solutions so that you truly learn how to work them out yourself in real scenarios.

So, there may be a more efficient solution than this; but here was my approach:

• Set a list to hold the previous row (initially empty).
• Loop up to the required depth from 1 to D inclusively.
  • Loop for each item that should be in that level (level 1 has 1 number, level N has N numbers).
  • If it’s an end-number add “1” to the new row, otherwise add the sum of parents.
• Print the new row.
• Store the new row as the previous row so it can be used for the next depth level’s parent calculations.

I’m sure you can do this without storing the previous row as well mathematically, but this is pretty elegant and will only take extra space equal to the sizeof(int) * level-number which is really nothing.

Java Solution

package john.humphreys;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class PascalsTriangle {

    public static void main(String[] args) {
        printToDepth(20);
    }

    private static void printToDepth(int d) {

        //Row 1 has value 1, anything less is invalid.
        if (d < 1) return;

        //Keep track of the previous row.
        List<Integer> previousRow = new ArrayList<>();

        //Loop from 1 to target depth inclusively.
        for (int i = 1; i <= d; ++i) {

            //Create a new row to populate with our solution.
            List<Integer> newRow = new ArrayList<>();

            //If this is a row-end (0 or max in row) add 0, otherwise add the parents' sum.
            for (int ri = 0; ri < i; ++ri) {
                newRow.add(ri == 0 || ri == i - 1 ? 1 : previousRow.get(ri - 1) + previousRow.get(ri));
            }

            //Print out the space-separated row.
            System.out.println(newRow.stream().map(Object::toString).collect(Collectors.joining(" ")));

            //Store this as the previous row.
            previousRow = newRow;
        }
    }
}

If we take out comments, gratuitous spacing, and imports, it’s quite lean:

public class PascalsTriangle {

    public static void main(String[] args) {
        printToDepth(20);
    }

    private static void printToDepth(int d) {
        if (d < 1) return;
        List<Integer> previousRow = new ArrayList<>();

        for (int i = 1; i <= d; ++i) {
            List<Integer> newRow = new ArrayList<>();
            for (int ri = 0; ri < i; ++ri) {
                newRow.add(ri == 0 || ri == i - 1 ? 1 : previousRow.get(ri - 1) + previousRow.get(ri));
            }
            System.out.println(newRow.stream().map(Object::toString).collect(Collectors.joining(" ")));
            previousRow = newRow;
        }
    }
}