How to generate Pascal's Triangle in Java

11/14/2018

In Pascal's triangle, the value from from every row is the sum of the values that are above it in the previous row. If no value is available one is used. Using the Java notation n[k] = n-1[k-1] + n-1[k]. The first row contains the value one.

Pascal's triangle is generated using 2 for loops and starting at the top with the first element.

Create the following java file:

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class InterviewPascalTriangle {

    protected List<List<Integer>> generatePascalTriangle(int nbRows){
	// Input Validation
	if ( nbRows < 0 )
	    throw new IllegalArgumentException( "The number of rows cannot be negative." );
	
	// The object to return
	List<List<Integer>> toReturn = new LinkedList<List<Integer>>();

	// Save the previous row.
	List<Integer> previousRow = Collections.emptyList();

	// Process all the rows
	for( int i = 0 ; i <= nbRows ; i++ ){
	    // Create the current row
	    List<Integer> currentRow = new LinkedList<Integer>();
	    toReturn.add( currentRow );

	    // Define the previous value
	    int previousValue = 0;
	    // Loop on all the values
	    for(int c : previousRow){
		currentRow.add( c + previousValue );
		
		// Set the current value as the previous one
		previousValue = c;
	    }


	    // Add the last value
	    currentRow.add( 1 );
	    
	    // Save the current row.
	    previousRow = currentRow;
	}
	
	return toReturn;
    }
    
   public static void main(String[] argv) throws Exception {
	InterviewPascalTriangle t = new InterviewPascalTriangle();

	
	List<List<Integer>> res = t.generatePascalTriangle(7);
	
	System.out.println( "Result:" );
	String tmp = res.get( res.size() -1 ).toString();
	
	int max = (int) tmp.length();
	
	for(List<Integer> c : res ){
	    String toDisplay = c.toString();
	    int padding = ( max - toDisplay.length()) / 2 ;
	    StringBuilder sb = new StringBuilder();
	    for(int i=0; i < padding; i++){
		sb.append( " " );
	    }
	    
	    sb.append( toDisplay );
	    
	    System.out.println( sb.toString() );
	}

    }



}

The output will be:

Result:
            [1]
           [1, 1]
         [1, 2, 1]
        [1, 3, 3, 1]
      [1, 4, 6, 4, 1]
    [1, 5, 10, 10, 5, 1]
  [1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]

The rows of Pascal's triangle are numbered from 0 to n. The first row only contains the value 1.

References:

Pascal's triangle

Recent Comments