Reasonable Solution O(n^2)


  • 0
    P

    Loop through all the rows from first to the one we want, and use the previous row's element to calculate current row element, and update result row every time. Looks much more reasonable than directly calculate a single row.

        public List<Integer> getRow(int rowIndex) {
            List<Integer> rst = new ArrayList<>();    
            // index to size
            rowIndex += 1;
            
            rst.add(1);
            
            for(int i = 1; i < rowIndex; i++){
                List<Integer> tmp = new ArrayList<>(i + 1);
                // fill
                for(int j = 0; j < i + 1; j++){
                    tmp.add(-1);
                }
                // front
                tmp.set(0, 1);
                // end
                tmp.set(i, 1);
                // middle
                for(int j = 1; j < i; j++){
                    tmp.set(j, rst.get(j) + rst.get(j - 1));
                }
                
                rst = tmp;
            }
            
            return rst;
        }
    

Log in to reply
 

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