O(n^2) Solution


  • 0
    S

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


  • 1
    S

    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>();
            first.add(1);
            output.add(first);
            
            for (int i = 1; i < numRows; i++) {
                ArrayList<Integer> al = new ArrayList<Integer>();
                al.add(1);    
                for (int j = 1; j < i; j++) {
                    ArrayList<Integer> prev = output.get(i-1);
                    al.add(prev.get(j-1) + prev.get(j));
                }
                al.add(1);
                output.add(al);
            }
            return output;
        }
    }

  • 0
    F

    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 ){
                    value.add(1);
                    ret.add(value);
                    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{
                            value.add(last.get(k-1)+last.get(k));
                        }
                    } 
                    ret.add(value);
                }
            
        }
        return ret;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.