Skip to content

118. Pascal's Triangle

DifficultyEasy

Description

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

Solutions

Solution 1: Simulation

Thinking

Row \(i\) is formed by adding adjacent entries of row \(i-1\), with \(1\)s on both ends. \(\textit{numRows}\le 30\), so building row by row is enough. Each row depends only on the previous one.

We first create an answer array \(f\), then set the first row of \(f\) to \([1]\). Next, starting from the second row, the first and last elements of each row are \(1\), and for other elements \(f[i][j] = f[i - 1][j - 1] + f[i - 1][j]\).

The time complexity is \(O(n^2)\), where \(n\) is the given number of rows. Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        f = [[1]]
        for i in range(numRows - 1):
            g = [1] + [a + b for a, b in pairwise(f[-1])] + [1]
            f.append(g)
        return f

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> f = new ArrayList<>();
        f.add(List.of(1));
        for (int i = 0; i < numRows - 1; ++i) {
            List<Integer> g = new ArrayList<>();
            g.add(1);
            for (int j = 1; j < f.get(i).size(); ++j) {
                g.add(f.get(i).get(j - 1) + f.get(i).get(j));
            }
            g.add(1);
            f.add(g);
        }
        return f;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> f;
        f.push_back(vector<int>(1, 1));
        for (int i = 0; i < numRows - 1; ++i) {
            vector<int> g;
            g.push_back(1);
            for (int j = 1; j < f[i].size(); ++j) {
                g.push_back(f[i][j - 1] + f[i][j]);
            }
            g.push_back(1);
            f.push_back(g);
        }
        return f;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func generate(numRows int) [][]int {
    f := [][]int{[]int{1}}
    for i := 0; i < numRows-1; i++ {
        g := []int{1}
        for j := 1; j < len(f[i]); j++ {
            g = append(g, f[i][j-1]+f[i][j])
        }
        g = append(g, 1)
        f = append(f, g)
    }
    return f
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function generate(numRows: number): number[][] {
    const f: number[][] = [[1]];
    for (let i = 0; i < numRows - 1; ++i) {
        const g: number[] = [1];
        for (let j = 1; j < f[i].length; ++j) {
            g.push(f[i][j - 1] + f[i][j]);
        }
        g.push(1);
        f.push(g);
    }
    return f;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
        let mut f = vec![vec![1]];
        for i in 1..num_rows {
            let mut g = vec![1];
            for j in 1..f[i as usize - 1].len() {
                g.push(f[i as usize - 1][j - 1] + f[i as usize - 1][j]);
            }
            g.push(1);
            f.push(g);
        }
        f
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    const f = [[1]];
    for (let i = 0; i < numRows - 1; ++i) {
        const g = [1];
        for (let j = 1; j < f[i].length; ++j) {
            g.push(f[i][j - 1] + f[i][j]);
        }
        g.push(1);
        f.push(g);
    }
    return f;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        var f = new List<IList<int>> { new List<int> { 1 } };
        for (int i = 1; i < numRows; ++i) {
            var g = new List<int> { 1 };
            for (int j = 1; j < f[i - 1].Count; ++j) {
                g.Add(f[i - 1][j - 1] + f[i - 1][j]);
            }
            g.Add(1);
            f.Add(g);
        }
        return f;
    }
}

Comments