C Solution and Optimization

• My original solution:

``````int** generate(int numRows, int** columnSizes) {
int **result = malloc(numRows * sizeof(int *));
*columnSizes = malloc(numRows * sizeof(int));

int n = 0;

(*columnSizes)[n] = 1;
result[n] = malloc(sizeof(int));
result[n][0] = 1;

for (++n; n < numRows; ++n) {
(*columnSizes)[n] = n + 1;
result[n] = malloc((n + 1) * sizeof(int));

for (int k = 0; k <= n; ++k) {
if (k == 0) {
result[n][k] = 1;
} else if (k == n) {
result[n][k] = 1;
} else {
result[n][k] = result[n - 1][k - 1] + result[n - 1][k];
}
}
}

return result;
}
``````

This gave me 3 ms runtime.

Too much mis-predication penalty in the for loop. Optimized to 0 ms:

``````int** generate(int numRows, int** columnSizes) {
int **result = malloc(numRows * sizeof(int *));
*columnSizes = malloc(numRows * sizeof(int));

int n = 0;

(*columnSizes)[n] = 1;
result[n] = malloc(sizeof(int));
result[n][0] = 1;

for (++n; n < numRows; ++n) {
(*columnSizes)[n] = n + 1;
result[n] = malloc((n + 1) * sizeof(int));

result[n][0] = 1;
result[n][n] = 1;
for (int k = 1; k < n; ++k) {
result[n][k] = result[n - 1][k - 1] + result[n - 1][k];
}
}

return result;
}
``````

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