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:

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.

Written on May 6, 2013