Wednesday, May 10, 2017

Pascal's Triangle II

Problem Statement

Given an index k, return the kth 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?
Link to GitHub :link

Pascal’s Triangle
Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.
ex of pascal triangle
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 


  • We need arrarlist
  • This arraylist row is used to add initial elements of the array
          row.add(0, 1)
          Note for the first 2 iterations elements would not be altered before adding to allrows
  • J loop iteration would not start till Row Size is greater than one. It is responsible to altering the arrraylist elements so to generate pascal triangle
  • The contents of the arraylist would be modified based on the size of the array.

public class PascalTriangle2 {
 public static List<Integer> get(int rowIndex){
  //Declare a new List
  List<Integer> list=new ArrayList<Integer>();
  if(rowIndex <0)
   return list;
  //Creation of Pascal triangle list
  for(int i=0;i< rowIndex+1;i++) 
   for(int j=1;j<list.size()-1;j++)
    list.set(j, list.get(j)+list.get(j+1));
  return list;

No comments:

Post a Comment