LeetCode Problem: Pascal’s Triangle II

By | 2013 年 1 月 17 日

Follow the algorithm in LeetCode Problem: Pascal’s Triangle, we can simple return the required row from the result.
从上一个题的算法LeetCode Problem: Pascal’s Triangle,可以得到一个简单的方法就是,在上一题的基础上,最后返回需要的行即可。

But, we can optimize this to use constant extra space, even better than the required O(k) extra space in the problem description below.


Take the above two rows as example, we can see that, the element in the last row is only relative to the element above it and the one before the element above it. So we can generate the last row from the previous row in backward order in place.Thus, we do not need the extra spaces.

Pascal’s Triangle II Oct 29 ’12
Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Could you optimize your algorithm to use only O(k) extra space?

Code, 16ms pass large test set

class Solution {
    vector getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector ret;
        if(rowIndex < 0) return ret;
        for(int ir = 0; ir <= rowIndex; ++ir) {
            //put an 1 at the end of this row
            //handle the rest of elements backward
            for(int ic = ir - 1; ic > 0; --ic) {
                ret[ic] = ret[ic] + ret[ic - 1];
        return ret;


电子邮件地址不会被公开。 必填项已用*标注