119. Pascal's Triangle II

Description

Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

Notice that the row index starts from 0.

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: rowIndex = 3

Output: [1, 3, 3, 1]

Example 2

Example 3

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

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

        return pascalsList;
    }
}

Solution 2

Follow up

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