119. Pascal's Triangle II

• Difficulty: Easy

• Topics: Array

• Similar Questions:

  • Pascal's Triangle

Problem:

Given a non-negative index k where k ≤ 33, return the k^th index row of the Pascal's triangle.

Note that the row index starts from 0.

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

Example:

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

Follow up:

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

Solutions:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1;
            for (int j = i-1; j > 0; --j) {
                row[j] = row[j] + row[j-1]; 
            }
        }

        return row;
    }
};