package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 119. Pascal's Triangle II
 * Given an index k, return the kth row of the Pascal's triangle.

 For example, given k = 3,
 Return [1,3,3,1].

 Note:
 Could you optimize your algorithm to use only O(k) extra space?
 */

public class _119 {

  public static class Solution1 {
    public List<Integer> getRow(int rowIndex) {
      if (rowIndex < 0) {
        return new ArrayList();
      }
      List<List<Integer>> result = new ArrayList();
      List<Integer> row = new ArrayList();
      row.add(1);
      result.add(row);
      for (int i = 1; i <= rowIndex; i++) {
        List<Integer> newRow = new ArrayList();
        newRow.add(1);
        List<Integer> lastRow = result.get(i - 1);
        for (int j = 1; j < lastRow.size(); j++) {
          newRow.add(lastRow.get(j - 1) + lastRow.get(j));
        }
        newRow.add(1);
        result.add(newRow);
      }
      return result.get(result.size() - 1);
    }
  }

  public static class Solution2 {
    /** O(k) space */
    public List<Integer> getRow(int rowIndex) {
      List<Integer> row = new ArrayList<>();
      for (int i = 0; i <= rowIndex; i++) {
        row.add(0, 1);
        for (int j = 1; j < row.size() - 1; j++) {
          row.set(j, row.get(j) + row.get(j + 1));
        }
      }
      return row;
    }
  }
}

@@ -85,232 +85,8 @@
 t;%0A%0A
-/**%0A * 119. Pascal's Triangle II%0A * Given an index k, return the kth row of the Pascal's triangle.%0A%0A For example, given k = 3,%0A Return %5B1,3,3,1%5D.%0A%0A Note:%0A Could you optimize your algorithm to use only O(k) extra space?%0A */%0A%0A
 publ
@@ -102,16 +102,18 @@
 _119 %7B%0A%0A
+  
   public
@@ -138,24 +138,28 @@
 tion1 %7B%0A    
+   
+ 
 public List%3C
@@ -186,24 +186,30 @@
 rowIndex) %7B%0A
+      
       if (ro
@@ -218,24 +218,32 @@
 ndex %3C 0) %7B%0A
+        
         retu
@@ -264,26 +264,38 @@
 st();%0A      
-%7D%0A
+      %7D%0A      
       List%3CL
@@ -336,24 +336,30 @@
 st();%0A      
+  
+    
 List%3CInteger
@@ -379,24 +379,30 @@
 rrayList();%0A
+      
       row.ad
@@ -409,24 +409,30 @@
 d(1);%0A      
+     
+ 
 result.add(r
@@ -432,24 +432,30 @@
 t.add(row);%0A
+      
       for (i
@@ -486,32 +486,40 @@
  i++) %7B%0A        
+       
+ 
 List%3CInteger%3E ne
@@ -534,32 +534,40 @@
 ew ArrayList();%0A
+        
         newRow.a
@@ -573,32 +573,40 @@
 add(1);%0A        
+      
+  
 List%3CInteger%3E la
@@ -632,32 +632,40 @@
 i - 1);%0A        
+     
+   
 for (int j = 1; 
@@ -693,32 +693,42 @@
 ++) %7B%0A          
+    
+      
 newRow.add(lastR
@@ -768,26 +768,37 @@
         
-%7D%0A
+        %7D%0A   
         
 newRow.a
@@ -781,32 +781,37 @@
    %7D%0A           
+     
 newRow.add(1);%0A 
@@ -809,32 +809,40 @@
 add(1);%0A        
+      
+  
 result.add(newRo
@@ -847,26 +847,38 @@
 Row);%0A      
-%7D%0A
+      %7D%0A      
       return
@@ -917,15 +917,23 @@
     
+ 
+   
 %7D%0A  
+ 
+ 
 %7D%0A%0A
+  
   pu
@@ -970,26 +970,54 @@
     
-/** O(k) space */%0A
+    /**%0A         * O(k) space%0A         */%0A    
     
@@ -1056,24 +1056,30 @@
 rowIndex) %7B%0A
+      
       List%3CI
@@ -1113,24 +1113,30 @@
 %3C%3E();%0A      
+ 
+     
 for (int i =
@@ -1153,32 +1153,40 @@
 owIndex; i++) %7B%0A
+        
         row.add(
@@ -1192,32 +1192,40 @@
 (0, 1);%0A        
+  
+      
 for (int j = 1; 
@@ -1257,24 +1257,34 @@
 %7B%0A          
+        
+  
 row.set(j, r
@@ -1320,24 +1320,46 @@
         
+        %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -1346,26 +1346,24 @@
     %7D%0A      
-%7D%0A
       return
@@ -1372,16 +1372,22 @@
 ow;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 119