Java 1 ms solution - Dynamic Programming


  • 0
    J

    This was my solution to the Pascal problem. Each row is built based on the previous row that is entered into the 'lists' data structure.

        public List<List<Integer>> generate(int numRows) {
            // create list data structure to hold rows
            List<List<Integer>> lists = new ArrayList<List<Integer>>();
            
            if(numRows == 0) {
                return lists;
            }
            
            // add base case: [1]
            List<Integer> rowOne = new ArrayList<Integer>();
            rowOne.add(1);
            lists.add(rowOne);
            if(numRows == 1) {
                return lists;
            }
            
            // add second base case: [1,1]
            List<Integer> rowTwo = new ArrayList<Integer>();
            rowTwo.add(1);
            rowTwo.add(1);
            lists.add(rowTwo);
            if(numRows == 2) {
                return lists;
            }
            
            // loop to calculate rows up to whatever the argument is
            for(int i = 2; i < numRows; i++) {
                // create new row list
                List<Integer> newList = new ArrayList<Integer>();
                // use previous row to calculate new row
                // make sure to increase previous row size by 1
                for(int j = 0; j < lists.get(i - 1).size() + 1; j++) {
                    // force the beginning and end of the new row to be 1
                    if(j == 0 || j == lists.get(i - 1).size()) {
                        newList.add(1);
                    } else {
                        // use previous values to calculate new values
                        newList.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
                    }
                }
                // add new row to the list
                lists.add(newList);
            }
            
            return lists;
        }

Log in to reply
 

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