# 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 *k*^{th} 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:

1
2
3
4
5
6
7
8

vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1);
for (int i = 2; i <= rowIndex; ++i) {
for (int j = i - 1; j > 0; --j)
row[j] = row[j] + row[j - 1];
}
return row;
}

## 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.