Pascal’s Triangle II

Problem

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:

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

Constraints

• 0 <= rowIndex <= 33

Solution

The problem Pascal's Triangle II can be solved intuitively by allocating the sum of the two numbers directly above to each index in array.

Implementation

class Solution
{
  public:
    vector<int> getRow(int rowIndex)
    {
        vector<int> ret(1, 1), row;
        for (int i = 1; i <= rowIndex; i++)
        {
            row = ret;
            ret.resize(i + 1, 1);

            for (int j = 1; j < i; j++)
                ret[j] = row[j - 1] + row[j];
        }
        return ret;
    }
};