2.Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

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

class Solution
{
public:
    vector<vector<int>> generate(int numRows)
    {

        vector<vector<int>> v;
        int i, j;
        for (i = 0; i < numRows; i++)
        {
            vector<int> k;
            for (j = 0; j <= i; j++)
            {
                if (i == j || j == 0)
                {
                    k.push_back(1);
                }
                else
                {
                    int s = v[i - 1][j] + v[i - 1][j - 1];
                    k.push_back(s);
                }
            }
            v.push_back(k);
        }

        return v;
    }
};

Time Complexity: O(N ^ 2) Space Complexity: O(N ^ 2)

Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

class Solution
{
public:
    vector<int> getRow(int rowIndex)
    {

        int i, j;
        vector<int> v;
        for (int i = 0; i <= rowIndex; i++)
        {

            vector<int> k;
            for (int j = 0; j <= i; j++)
            {

                if (j == 0 || i == j)
                {
                    k.push_back(1);
                }
                else
                {
                    int s = v[j - 1] + v[j];
                    k.push_back(s);
                }
            }
            v = k;
        }

        return v;
    }
};

Time Complexity: O(N ^ 2) Space Complexity: O(N)