# O(n^2) Solution

• Here is my O(N^2) Solution. I had a little bit of hard time resolving ArrayIndexOutOfBound Exception.

• I guess the code attached below is more self-explanatory but to word out the algorithm that I used is:

• insert 1 in first row
• insert 1 in first column for each row
• insert sum previous row's j-1 and j in row i and column j
• insert 1 in last column for each row

Solution is O(n^2), I think.

``````public class Solution {
public ArrayList<ArrayList<Integer>> generate(int numRows) {
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
if (numRows <= 0) return output;

ArrayList<Integer> first = new ArrayList<Integer>();

for (int i = 1; i < numRows; i++) {
ArrayList<Integer> al = new ArrayList<Integer>();
for (int j = 1; j < i; j++) {
ArrayList<Integer> prev = output.get(i-1);
}
}
return output;
}
}``````

• i think you can use this.

public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();

``````    if( numRows== 0 ) return ret;

for ( int i = 0; i < numRows; i++ ){
List<Integer> value = new ArrayList<Integer>();
if ( i == 0 ){
continue;
} else {
List<Integer> last = ret.get(ret.size()-1);
for ( int k = 0; k <= i; k++ ){
if ( k == 0 ) value.add(1);
else if( k == i ) value.add(1);
else{
}
}