[Triangle] Pascal's Triangle II

1. Example
k =3
return [1,3,3,1]

[
[1],
[1,1],
[1,2,1],
[1,3,3,1]   <= k=3
]

2. Implementation
only O(k) extra space since if use Pascal's Triangle I's method, space:O(n)
cannot have a new List<Integer> for every row, so keep overwriting the existing one
List<Integer> would only keep current list element so for k =3 only keep 4 elements


// NOTE: first row refers to k = 0

// NOTE: forward iterating would race

// NOTE: 3(idx=2) = 1(idx=2) + 2(idx=1)

// NOTE: 3(idx=2) = 2(idx=1) + 1(idx=2)
// NOTE: snippet
for (i = pre.size() -1 ; i > 0; i--) { 

   pre.set( i ,pre.get(i) + pre.get(i-1) ); 

 } 

pre.add(1);

// time :O(n^2), Space:O(k)
public List generate(int k)
{
     List pre = new ArrayList();
     // validate the input
     // NOTE: first row refers to k = 0
     if ( k < 0 )
     { 
         return pre;
     }
      


     pre.add(1);



      
     for(int i = 1 ; i <= k;k++)
     {


         // NOTE: forward iterating would race 
         //for (int i = 0 ; i < pre.size() ; i ++ )
         // NOTE: 3(idx=2) = 1(idx=2) + 2(idx=1) 
         for (i = pre.size() -1 ; i > 0; i--)
         {
             pre.set( i  ,pre.get(i) + pre.get(i-1)  ); 
         }
         pre.add(1);



     }
    
     return pre;
}

// NOTE: 3(idx=2) =   2(idx=1) + 1(idx=2) 
for ( i = pre.size()-2; i >=0 ;i--)
{
    pre.set(i+1,  pre.get(i) + pre.get(i+1)   );
}

3. Similar Ones:
Pascal's Triangle I