119. Pascal's Triangle II

2020, Dec 04 One min read

1. Description

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
PascalTriangle

2. Example

Example 1

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2

Input: rowIndex = 0
Output: [1]

Example 3

Input: rowIndex = 1
Output: [1,1]

3. Constraints

0 <= rowIndex <= 33

4. Follow Up

Could you optimize your algorithm to use only O(rowIndex) extra space?

5. Solutions

Array (Follow Up)

n = rowIndex
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// when we calculate one row in the Pascal's triangle, we only need the last row
// so we just need to use two rows' space
// further more, we actually just need one row, we could calculate a row from back to front
// so we could just a single row's space
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

Search

Tags