Pascal's Triangle

• LeetCode: Pascal's Triangle

• Problem:

Given numRows, generate the first numRows of Pascal's triangle.

• Examples:

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

• Analysis:

list[i][j] is the j th item in a list at row i.

list[i][j] = list[i - 1][j - 1] + list[i - 1][j]

• Code - Java:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(1);
            if (i == 0) {
                results.add(temp);
                continue;
            } else if (i > 1) {
                List<Integer> last = results.get(i - 1);
                for (int j = 1; j < i; j++) {
                    temp.add(last.get(j - 1) + last.get(j));
                }
            }
            temp.add(1);
            results.add(temp);
        }
        return results;
    }
}

• Code - C++:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> results;
        for (int i = 0; i < numRows; i++) {
            vector<int> temp;
            temp.push_back(1);
            if (i == 0) {
                results.push_back(temp);
                continue;
            } else if (i > 1) {
                vector<int> last = results[i - 1];
                for (int j = 1; j < i; j++) {
                    temp.push_back(last[j - 1] + last[j]);
                }
            }
            temp.push_back(1);
            results.push_back(temp);
        }
        return results;
    }
};

• Code - Python:

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        results = []
        for i in range(numRows):
            temp = [1]
            if i == 0:
                results.append(temp)
                continue
            elif i > 1:
                last = results[i - 1]
                for j in range(1, i):
                    temp.append(last[j - 1] + last[j])
            temp.append(1)
            results.append(temp)
        return results

• Time Complexity: O(N^2), N is the numRows

• Space Complexity: O(N^2), N is the numRows