Pascal's Triangle II

Given a non-negative index k where k≤ 33, return the _k_th index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input:
 3

Output:
 [1,3,3,1]

Follow up:

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

Analysis

Dynamic Programming

Same as Pascal's Triangle I, just need to use current row and previous row in order to get O(k) space complexity.

Math

Or using math (https://leetcode.com/problems/pascals-triangle-ii/discuss/38513/My-clean-O(k)-java-solution?orderBy=most_votes\:

row k of Pascal's Triangle:

[C(k,0), C(k,1), ..., C(k, k-1), C(k, k)]

and

C[k,i] = C[k,i-1]*(k-i+1)/i

Solution

O(K) space O(K^2) time (3ms 11.27%) - 在首位加1，内层循环正序即可

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            row.add(0, 1);
            for (int j = 1; j < i; j++) {
                row.set(j, row.get(j) + row.get(j + 1));
            }
        }
        return row;
    }
}

Same approach - Another One 在末尾加1， 内层循环要从末尾倒序循环

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; i++) {
            res.add(1);
            for (int j = i - 1; j >= 1; j++) {
                res.set(j, res.get(j - 1) + res.get(j));
            }
        }
        return res;
    }
}

O(K) space and O(K) time using Math (1ms 91.55%)

class Solution {
        public List<Integer> getRow(int rowIndex) {
            Integer[] rowList = new Integer[rowIndex+1];
            rowList[0] = 1;
            for(int i=1; i<rowList.length;i++) {
                rowList[i] = (int)((long)rowList[i-1]*(rowIndex-(i-1))/(i));
            }
            return Arrays.asList(rowList);
        }
    }

O(K) space and O(K^2) (0ms 100%)

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[] res = new int[rowIndex+1];
        res[0] = 1;
        for(int i=1; i<rowIndex+1; i++)
            for(int j=i; j>=1; j--)
                res[j] += res[j-1];
        List<Integer> list = new ArrayList<> ();
        for(int n : res) {
            list.add(n);
        }
        return list;
    }
}

Traditional 2D DP - storing dp[][] element for each layer - O(n^2) time, and O(n^2) space - (1ms AC)

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>();
        int[][] dp = new int[rowIndex + 1][rowIndex + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        for (int k = 0; k <= rowIndex; k++) {
            ans.add(dp[rowIndex][k]);
        }
        return ans;
    }
}

Reference

Wikipedia: [Pascal's Triangle]([https://en.wikipedia.org/wiki/Pascal's_triangle](https://en.wikipedia.org/wiki/Pascal's_triangle)\)