Algorithm Puzzles: Pascal's Triangle

Posted on In Views: Word count in article: 129 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Pascal’s Triangle

Puzzle

Puzzle from leetcode:

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:

1
2
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

1
2
Input: numRows = 1
Output: [[1]]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret{{1}};

        if(numRows >= 2) {
            ret.emplace_back(std::vector<int>(2, 1));
        }

        for(int i = 2; i < numRows; ++i) {
            ret.emplace_back(std::vector<int>(ret[i-1].size() + 1, 1));
            for(int j = 1; j < ret[i].size() - 1; j++) {
                ret[i][j] = ret[i-1][j-1] + ret[i-1][j];
            }
        }

        return ret;
    }
};

T.C.: O(N * N)