# LeetCode Pascal’s Triangle I and II: Array Operation

## Overview

This LeetCode Pascal’s Triangle problem is to test your array operation skills and to get the k-th row, we only need an extra array of size k + 1.

## LeetCode Pascal’s Triangle Problem

(1)Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

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

(2)
Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return `[1,3,3,1]`.

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

## Solution and Analysis

This is a simple problem, and the pattern of Pascal’s triangle is easy to figure out: the i-th row has (i+1) numbers (i starting from zero), except the first and second row, all the other rows say j-th row (j > 1), the elements in j-th row is that row[j][0] = row[j][j] = 1, row[j][k] = row[j-1][k-1] + row[j-1][k] where j > 1 for k >0 && k < j.

For the second problem, to get the k-th row, we only need to know the (k-1)-th row, we obviously don’t have to keep the whole Pascal’s triangle, thus O(2k) space like two vectors and each is of size k, is enough for us to get the k-th row. We just swap these two rows iteratively and get the final k-th row in Pascal’s triangle.

Well the memory cost could still be optimized, the key is to “shift” the row array by one position, the following code less than 6 lines of code is accepted by the LeetCode OJ to pass the Pascal’s Triangle II problem, for the Pascal’s Triangle I, it is not hard to tack at all, so I do not bother to give the source code:

## Summary

This LeetCode Pascal’s Triangle problem is to test your array operation skills and to get the k-th row, we only need an extra array of size k + 1. I just summarized all different methods here.

Written on May 6, 2013