Pascal's Triangle II

Problem Statement

Constraints

Solution 1: Iterative Construction

function getRowIterative(rowIndex) {
    const row = [1];
    for (let i = 1; i <= rowIndex; i++) {
        const newRow = [];
        for (let j = 0; j <= i; j++) {
            if (j === 0 || j === i) {
                newRow.push(1);
            } else {
                newRow.push(row[j - 1] + row[j]);
            }
        }
        row.length = 0;
        row.push(...newRow);
    }
    return row;
} 

const rowIndex1 = 3;
getRowIterative(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowIterative(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowIterative(rowIndex3);  //output: [1,1] 

Solution 2: Combinatorial Approach

function getRowCombinatorial(rowIndex) {
    const row = [];
    let value = 1;
    for (let i = 0; i <= rowIndex; i++) {
        row.push(value);
        value = value * (rowIndex - i) / (i + 1);
    }
    return row;
} 

const rowIndex1 = 3;
getRowCombinatorial(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowCombinatorial(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowCombinatorial(rowIndex3);  //output: [1,1] 

Solution 3: Recursive Approach

function getRowRecursive(rowIndex) {
    if (rowIndex === 0) return [1];
    const prevRow = getRowRecursive(rowIndex - 1);
    const row = [1];
    for (let i = 1; i < rowIndex; i++) {
        row.push(prevRow[i - 1] + prevRow[i]);
    }
    row.push(1);
    return row;
} 

const rowIndex1 = 3;
getRowRecursive(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowRecursive(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowRecursive(rowIndex3);  //output: [1,1] 

Solution 4: In-place Update Approach

function getRowInPlace(rowIndex) {
    const row = new Array(rowIndex + 1).fill(1);
    for (let i = 1; i < rowIndex; i++) {
        for (let j = i; j > 0; j--) {
            row[j] += row[j - 1];
        }
    }
    return row;
} 

const rowIndex1 = 3;
getRowInPlace(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowInPlace(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowInPlace(rowIndex3);  //output: [1,1] 

Solution 5: Using Factorials

function getRowFactorials(rowIndex) {
    function factorial(n) {
        let result = 1;
        for (let i = 2; i <= n; i++) result *= i;
        return result;
    }
    
    const row = [];
    for (let i = 0; i <= rowIndex; i++) {
        row.push(factorial(rowIndex) / (factorial(i) * factorial(rowIndex - i)));
    }
    return row;
} 

const rowIndex1 = 3;
getRowFactorials(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowFactorials(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowFactorials(rowIndex3);  //output: [1,1] 

Solution 6: DFS with Memoization for Pascals Triangle Row

function getRowDFSMemo(rowIndex) {
    const memo = new Map();
    const result = [];

    for (let i = 1; i <= rowIndex + 1; i++) {
        result.push(dfsHelper(rowIndex + 1, i));
    }

    return result;

    function dfsHelper(row, col) {
        if (row === col || col === 1) {
            return 1;
        }
        
        const key = `${row},${col}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        const result = dfsHelper(row - 1, col - 1) + dfsHelper(row - 1, col);
        memo.set(key, result);
        
        return result;
    }
} 

const rowIndex1 = 3;
getRowDFSMemo(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowDFSMemo(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowDFSMemo(rowIndex3);  //output: [1,1] 

Solution 7: Combination Formula Approach for Pascal Triangle Row

function getRowCombinationFormula (n) {
    function comb(n, k) {
        if (k > n - k) k = n - k; // Take advantage of symmetry
        let c = 1;
        for (let i = 0; i < k; i++) {
            c = c * (n - i) / (i + 1);
        }
        return c;
    }

    return Array.from({ length: n + 1 }, (_, x) => comb(n, x));
} 

const rowIndex1 = 3;
getRowCombinationFormula(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowCombinationFormula(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowCombinationFormula(rowIndex3);  //output: [1,1] 

Solution 8: Dynamic Programming Approach

function getRowDP(rowIndex) {
    const numRows = rowIndex + 1;
    const pascal = Array.from({ length: numRows }, () => Array(numRows).fill(0));
    
    for (let i = 0; i < numRows; i++) {
        pascal[i][0] = pascal[i][i] = 1;
        for (let j = 1; j < i; j++) {
            pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
        }
    }
    
    return pascal[rowIndex].slice(0, rowIndex + 1);
} 

const rowIndex1 = 3;
getRowDP(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRowDP(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRowDP(rowIndex3);  //output: [1,1] 

Solution 9: Iterative Approach for Generating a Specific Row of Pascals Triangle

function getRow(rowIndex) {
    if (rowIndex === 0) return [1];
    if (rowIndex === 1) return [1, 1];
    
    const row = [1, 1];
    let n = row.length;
    
    while (n - 1 !== rowIndex) {
        row.push(1);
        let prev = 1;
        for (let i = 1; i < n; i++) {
            const temp = row[i];
            row[i] = row[i] + prev;
            prev = temp;
        }
        n = row.length;
    }
    
    return row;
} 

const rowIndex1 = 3;
getRow(rowIndex1);  //output: [1,3,3,1] 

const rowIndex2 = 0;
getRow(rowIndex2);  //output: [1] 

const rowIndex3 = 1;
getRow(rowIndex3);  //output: [1,1] 

More Problems Solutions