118. Pascals Triangle - Explanation

Description

You are given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1

Output: [[1]]

Constraints:

1 <= numRows <= 30

Topics

Array Dynamic Programming

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming - Building each row using values from the previous row
2D Arrays - Storing and accessing the triangle structure
Combinatorics - Understanding that each element is a binomial coefficient C(n, k) and can be computed incrementally

1. Combinatorics

Intuition

Each element in Pascal's Triangle corresponds to a binomial coefficient. The value at row n and position k is C(n, k). Rather than computing each coefficient from scratch using factorials, we can compute them incrementally. Starting from 1, each subsequent value in a row can be derived by multiplying by (n - k + 1) / k.

Algorithm

Initialize an empty result list.
For each row n from 0 to numRows - 1:
- Start the row with [1].
- Set val = 1.
- For each position k from 1 to n:
  - Compute val = val * (n - k + 1) / k.
  - Append val to the row.
- Add the completed row to the result.
Return the result list.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for n in range(numRows):
            row = [1]
            val = 1
            for k in range(1, n + 1):
                val = val * (n - k + 1) // k
                row.append(val)
            res.append(row)
        return res

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int n = 0; n < numRows; n++) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            int val = 1;
            for (int k = 1; k <= n; k++) {
                val = val * (n - k + 1) / k;
                row.add(val);
            }
            res.add(row);
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for (int n = 0; n < numRows; n++) {
            vector<int> row;
            row.push_back(1);
            int val = 1;
            for (int k = 1; k <= n; k++) {
                val = val * (n - k + 1) / k;
                row.push_back(val);
            }
            res.push_back(row);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} numRows
     * @return {number[][]}
     */
    generate(numRows) {
        let res = [];
        for (let n = 0; n < numRows; n++) {
            let row = [1];
            let val = 1;
            for (let k = 1; k <= n; k++) {
                val = (val * (n - k + 1)) / k;
                row.push(val);
            }
            res.push(row);
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> Generate(int numRows) {
        var res = new List<List<int>>();
        for (int n = 0; n < numRows; n++) {
            var row = new List<int> { 1 };
            int val = 1;
            for (int k = 1; k <= n; k++) {
                val = val * (n - k + 1) / k;
                row.Add(val);
            }
            res.Add(row);
        }
        return res;
    }
}

func generate(numRows int) [][]int {
    res := make([][]int, 0)
    for n := 0; n < numRows; n++ {
        row := []int{1}
        val := 1
        for k := 1; k <= n; k++ {
            val = val * (n - k + 1) / k
            row = append(row, val)
        }
        res = append(res, row)
    }
    return res
}

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        for (n in 0 until numRows) {
            val row = mutableListOf(1)
            var value = 1
            for (k in 1..n) {
                value = value * (n - k + 1) / k
                row.add(value)
            }
            res.add(row)
        }
        return res
    }
}

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var res = [[Int]]()
        for n in 0..<numRows {
            var row = [1]
            var val = 1
            for k in 1...max(1, n) {
                if k > n { break }
                val = val * (n - k + 1) / k
                row.append(val)
            }
            res.append(row)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

2. Dynamic Programming - I

Intuition

Each element in Pascal's Triangle (except the edges) is the sum of the two elements directly above it. We can simulate this by padding the previous row with zeros on both ends, then summing adjacent pairs to generate the next row.

Algorithm

Start with the first row [[1]].
For each subsequent row:
- Take the last row and pad it with zeros: [0] + row + [0].
- Create a new row by summing adjacent elements: temp[j] + temp[j + 1].
- Append the new row to the result.
Return the result after generating numRows rows.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]

        for i in range(numRows - 1):
            temp = [0] + res[-1] + [0]
            row = []
            for j in range(len(res[-1]) + 1):
                row.append(temp[j] + temp[j + 1])
            res.append(row)
        return res

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        res.get(0).add(1);

        for (int i = 1; i < numRows; i++) {
            List<Integer> temp = new ArrayList<>(res.get(i - 1));
            temp.add(0, 0);
            temp.add(0);
            List<Integer> row = new ArrayList<>();

            for (int j = 0; j < res.get(i - 1).size() + 1; j++) {
                row.add(temp.get(j) + temp.get(j + 1));
            }

            res.add(row);
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res = {{1}};

        for (int i = 0; i < numRows - 1; i++) {
            vector<int> temp = {0};
            temp.insert(temp.end(), res.back().begin(), res.back().end());
            temp.push_back(0);
            vector<int> row;
            for (size_t j = 0; j < res.back().size() + 1; j++) {
                row.push_back(temp[j] + temp[j + 1]);
            }
            res.push_back(row);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} numRows
     * @return {number[][]}
     */
    generate(numRows) {
        let res = [[1]];

        for (let i = 0; i < numRows - 1; i++) {
            let temp = [0, ...res[res.length - 1], 0];
            let row = [];
            for (let j = 0; j < res[res.length - 1].length + 1; j++) {
                row.push(temp[j] + temp[j + 1]);
            }
            res.push(row);
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> Generate(int numRows) {
        var res = new List<List<int>>();
        if (numRows <= 0) return res;

        res.Add(new List<int> { 1 });

        for (int i = 1; i < numRows; i++) {
            var prev = res[i - 1];
            var temp = new List<int>(prev);
            temp.Insert(0, 0);
            temp.Add(0);

            var row = new List<int>();
            for (int j = 0; j < prev.Count + 1; j++) {
                row.Add(temp[j] + temp[j + 1]);
            }
            res.Add(row);
        }

        return res;
    }
}

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val res = mutableListOf(listOf(1))

        for (i in 0 until numRows - 1) {
            val temp = listOf(0) + res.last() + listOf(0)
            val row = mutableListOf<Int>()
            for (j in 0 until res.last().size + 1) {
                row.add(temp[j] + temp[j + 1])
            }
            res.add(row)
        }
        return res
    }
}

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var res = [[1]]

        for i in 0..<numRows - 1 {
            let temp = [0] + res.last! + [0]
            var row = [Int]()
            for j in 0..<res.last!.count + 1 {
                row.append(temp[j] + temp[j + 1])
            }
            res.append(row)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming - II

Intuition

We directly apply the defining property of Pascal's Triangle: each interior element equals the sum of the two elements above it. The first and last elements of every row are always 1. We build row by row, referencing the previous row for the sums.

Algorithm

Initialize a 2D list where row i has i + 1 elements, all set to 1.
For each row from index 2 onward:
- For each interior position j (not the first or last):
  - Set res[i][j] = res[i - 1][j - 1] + res[i - 1][j].
Return the completed triangle.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1] * (i + 1) for i in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, i):
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j]
        return res

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(row);
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);

        for (int i = 0; i < numRows; i++) {
            res[i].resize(i + 1);
            res[i][0] = res[i][i] = 1;
            for (int j = 1; j < i; j++){
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} numRows
     * @return {number[][]}
     */
    generate(numRows) {
        let res = Array.from({ length: numRows }, (_, i) =>
            Array(i + 1).fill(1),
        );

        for (let i = 2; i < numRows; i++) {
            for (let j = 1; j < i; j++) {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> Generate(int numRows) {
        var res = new List<List<int>>();
        for (int i = 0; i < numRows; i++) {
            var row = new List<int>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.Add(1);
                } else {
                    row.Add(res[i - 1][j - 1] + res[i - 1][j]);
                }
            }
            res.Add(row);
        }
        return res;
    }
}

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = MutableList(i + 1) { 1 }
            for (j in 1 until i) {
                row[j] = res[i - 1][j - 1] + res[i - 1][j]
            }
            res.add(row)
        }
        return res
    }
}

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var res = [[Int]]()
        for i in 0..<numRows {
            var row = [Int](repeating: 1, count: i + 1)
            for j in 1..<i {
                row[j] = res[i - 1][j - 1] + res[i - 1][j]
            }
            res.append(row)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Common Pitfalls

Off-by-One Errors with Row Indexing

Pascal's Triangle is often 0-indexed, so row 0 is [1], row 1 is [1, 1], and so on. Confusing 0-indexed and 1-indexed row numbering leads to generating one too many or one too few rows. Always clarify whether numRows means the count of rows or the index of the last row.

Forgetting Edge Elements Are Always 1

The first and last elements of every row are always 1. When building rows iteratively, only the interior elements (positions 1 through i-1 for row i) need to be computed as sums. Attempting to compute edge elements using the sum formula causes index-out-of-bounds errors.