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
YouTube
Examples
Input: rowIndex = 3
Output: [1, 3, 3, 1]
Input: rowIndex = 0
Output: [1]
Input: rowIndex = 1
Output: [1, 1]
Solutions
/**
* 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;
}
}
/**
* 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?
