LeetCode #118 Pascal’s Triangle

Easy

Problem

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.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution

Use dynamic programming approach. We don’t recursively calculate values but use information of last level to calculate current level information.

The equation of calculating new information is:

matrix[row][col] = matrix[row-1][col-1] + matrix[row-1][col]

Complexity

Line 18 will be executed row — 2 times, and value of row is between 2 and n-1 which n is numRows. It means Line 18 will run 1+ 2 + … + (n-2) = O((n-2)*(n-1) / 2) = O(n²). Therefore time complexity is O(n²).

Moreover, we use O(n(n+1)/2) space for saving result so space complexity is O(n²) as well.