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

Input: rowIndex = 0

Output: [1]

Example 3

Input: rowIndex = 1

Output: [1, 1]

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

/**
 * Time complexity : O(k^2). Same as the previous dynamic programming approach.
 * Space complexity : O(k). No extra space is used other than that required 
 *    to hold the output.
 */

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

        return pascals;
    }
}

Follow up

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