In Pascal's triangle, each number is the sum of the two numbers directly above it.
Last updated
/**
* 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;
}
}