Coding Interview Prep: Pascal’s Triangle with JavaScript Solution

Solution

/*
Time Complexity: O(n^2)
Space Complexity: O(n^2)
 */
var generate = function(numRows) {
        if (numRows === 0){
            return [];
        }
        if (numRows === 1){
            return [[1]];
        }

        let prevRows = generate(numRows-1);
        let prevRow = prevRows[prevRows.length-1];
        let currentRow = [1];

        for (let i=1; i<numRows-1; i++){
            currentRow.push(prevRow[i-1]+prevRow[i]);
        }
        currentRow.push(1);
        prevRows.push(currentRow);
        return prevRows;
};

Explanation

There are the base cases of numRows equals to 0 or 1 in the beginning of the method. Then the generate method is called recursively so that the previous rows can be retrieved. The last previous row is retrieved and declared into a variable to create the currentRow. As we know, the first and last index of the array consists of just 1. The indices in between will be the sum of the previous row.

The time complexity is O(n²), n is the number of rows. The space complexity is also O(n²).