# Here is my O(n) solution and the proof

• the mth element of the nth row of the Pascal's triangle is C(n, m) = n!/(m! * (n-m)!)

C(n, m-1) = n!/((m-1)! * (n-m+1)!)

so C(n, m) = C(n, m-1) * (n-m+1) / m

In additional, C(n, m) == C(n, n-m)

``````  class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row;
if(rowIndex < 0) {
return row;
}
row.resize(rowIndex + 1);
row[0] = row[rowIndex] = 1;
for(int m =1; m < rowIndex /2 + 1; m++) {
row[m] = row[rowIndex - m] = ((long long int)row[m - 1] * (rowIndex - m + 1)) / m;
}
return row;
}
};``````

• I had similar idea but in Java. O(n) time and O(1) space.

``````public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> resultList = new ArrayList<Integer>();
if (rowIndex==0){
return resultList;
}

int num = rowIndex/2;
long temp = 1; // Some test cases have numbers larger than Integer.MAX_VALUE

// Compute first half using C(n, m) = C(n, m-1) * (n-m+1) / m;
for(int i = 1; i<=num; i++){
temp*=rowIndex-i+1;
temp/=i;
}

// Mirror the second half
for(int i = (rowIndex-1)/2; i>=0; i--){
}

return resultList;
}
}``````

• Very good formula deriving. It's actually also shown in wikipedia Pascal Triangle entry.

Here is the C version:

``````int *getRow(int rowIndex, int *returnSize) {
// For row n, the k th element, the entry is the product of its previous entry and (n  + 1 - k)/k.
*returnSize = rowIndex + 1;
int *row = malloc(*returnSize * sizeof(int));

int k = 0;
row[k] = 1;

while (++k < *returnSize) {
row[k] = (unsigned long long)row[k - 1] * (*returnSize - k) / k;
}

return row;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.