Generating Pascal's Triangle in C99

Question

I recently completed the Pascal's Triangle challenge on leetcode. I would like to have my code reviewed.

You don't need a leetcode account to see the description of the challenge linked above, but for completeness I'm pasting the description here.

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

I think your review should touch the following points:

• Code correctness (the code passed all leetcode tests, but there might be some bug/UB hiding somewhere that neither I nor leetcode caught)
• Code performance (algorithm and implementation details)
• Code quality (the so-called "best practices" -- it's okay to be subjective)
• Stick to C99 without compiler extensions or anything non-standard

I encourage you to be pedantic about UB, memory management, adherence to the C standard, etc.

One last note: Leetcode forces me to use this exact function signature

int **generate(int numRows, int *returnSize, int **returnColumnSizes);

So that's something I can't change.

Finally, here's my code:

// solution.c

#include <stdlib.h>
#include <string.h>

int **generate(int numRows, int *returnSize, int **returnColumnSizes)
{
    int **ret = malloc((size_t)numRows * sizeof(int *));
    *returnColumnSizes = malloc((size_t)numRows * sizeof(int));
    *returnSize = numRows;

    for (size_t i = 0; i < numRows; i += 1)
    {
        size_t size = i + 1;
        (*returnColumnSizes)[i] = (int)size;
        ret[i] = malloc((size_t)size * sizeof(int));
        ret[i][0] = 1;
        ret[i][i] = 1;

        for (size_t j = 1; j < i; j += 1)
        {
            ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
        }
    }

    return ret;
}

Here's the driver code I used to test it:

// main.c

#include <stdlib.h>
#include <stdio.h>

int **generate(int numRows, int *returnSize, int **returnColumnSizes);

int main()
{
    int *returnColumnSizes;
    int returnSize;

    int **rows = generate(5, &returnSize, &returnColumnSizes);

    for (size_t i = 0; i < returnSize; i += 1)
    {
        for (size_t j = 0; j < returnColumnSizes[i]; j += 1)
        {
            printf("%d ", rows[i][j]);
        }

        free(rows[i]);

        printf("\n");
    }

    free(rows);

    return EXIT_SUCCESS;
}

Here's how I compile and run the code:

# run.sh

CC="clang"
CFLAGS="-std=c99 -Werror -Wall -Wpedantic -Wconversion"

$CC $CFLAGS ./solution.c ./main.c -o ./main && ./main

./run.sh

Answer 1

pedantic about UB, memory management, adherence to the C standard, etc.

Be careful about requesting pedantic, lots of corners.

Consider enabling more warnings

// -Wall -Wpedantic -Wconversion
-pedantic -Wall -Wextra -Wconversion -Wformat 

int overflow is UB

Test for potential overflow.

// ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
if (ret[i - 1][j - 1] > INT_MAX - ret[i - 1][j]) {
  // Handle overflow with TBD code.
  // Maybe free allocations and return NULL
  return NULL;
}
ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];

Missing range test

If numRows < 0, code has troubles. Better to detect.

if (numRows < 0) return NULL;

Code may also want to reject numRows == 0, yet robust code would elegantly handle this case.

Missing allocation test

Allocation failed to check for success before using the pointer.

int **ret = malloc((size_t)numRows * sizeof(int *));

// Add
if (ret == NULL && numRows > 0) {
  // TBD Error handling.
  return NULL;
}
...
ret[i] = ...

Driver code should check for a NULL return from generate().

Avoid mixing types

numRows is an int. Use an int iterator. ++ is a common C idiom.

// for (size_t i = 0; i < numRows; i += 1)
for (int i = 0; i < numRows; i++)

This also avoids the cast. Casts hint that code is doing something wrong.

// (*returnColumnSizes)[i] = (int)size;
(*returnColumnSizes)[i] = size;

Pedantic: size_t may be narrower than int

(size_t)numRows may truncate numRows.

Handled in next point.

Pedantic: Detect potential overflow

(size_t)numRows * sizeof(int *) may overflow.

// int **ret = malloc((size_t)numRows * sizeof(int *));
if (numRows < 0) return 0;
if ((unsigned) numRows > SIZE_MAX/sizeof ret[0]) return 0;
int **ret = malloc(sizeof ret[0] * (unsigned)numRows);
if (ret == NULL && numRows > 0) return 0;

    

---

Other:

Avoid unnecessary casts

size is already a size_t. No need to cast it to size_t.

size_t size = i + 1;
...
// ret[i] = malloc((size_t)size * sizeof(int));
ret[i] = malloc(size * sizeof(int));

Allocate to the referenced data, not the type.

Easier to code right, review and maintain.

// *returnColumnSizes = malloc((size_t)numRows * sizeof(int));
*returnColumnSizes = malloc(sizeof (*returnColumnSizes)[0] * numRows);
// or
*returnColumnSizes = malloc(sizeof returnColumnSizes[0][0] * numRows);

Answer 2

Advice I (Memory usage)

For a Pascal's triangle of \$N\$ rows, your solution allocates \$N²\$ elements worth of data. You could reduce it to \$½N(N + 1)\$. (See the Alternative implementation.)

Advice II: On main.c

In main.c, you write:

for (size_t i = 0; i < returnSize; i += 1) 

Why not i++ instead of i += 1? Same applies to

for (size_t j = 0; j < returnColumnSizes[i]; j += 1)

Also, what comes to naming, I suggest you rename i to level and j to column.

When it comes to the inner loop, you don't need

for (size_t j = 0; j < returnColumnSizes[i]; j += 1)

You could just do

for (size_t j = 0; j <= i; j++)

Finally, instead of printf("\n"), you could just write puts("").

Advice III: On solution.c

First of all, I would split solution.c into two files:

• pascals_triangle.h which contains the solution function declaration,
• pascals_triangle.c which contains the solution function definition.

In pascals_triangle.c, I would rename i to level and j to column. Otherwise, it seems O.K.

Alternative implementation

Summa summarum, I thought about the following:

pascals_triangle.h:

#ifndef COM_GITHUB_CODERODDE_FUN_PASCALS_TRIANGLE
#define COM_GITHUB_CODERODDE_FUN_PASCALS_TRIANGLE

int** generate(int numRows, int* returnSize, int** returnColumnSizes);

#endif /* COM_GITHUB_CODERODDE_FUN_PASCALS_TRIANGLE */

pascals_triangle.c:

#include "pascals_triangle.h"
#include <stdlib.h>

int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
    int** pascals_triangle = malloc(sizeof(int*) * numRows);
    *returnColumnSizes = malloc(numRows * sizeof(int));
    *returnSize = numRows;

    for (int level = 0; level < numRows; level++)
    {
        int size = level + 1;
        (*returnColumnSizes)[level] = size;
        pascals_triangle[level] = malloc(sizeof(int) * size);
        
        pascals_triangle[level][0] =
        pascals_triangle[level][level] = 1;

        for (int column = 1; column < level; column++)
        {
            pascals_triangle[level][column] =
                pascals_triangle[level - 1][column - 1] +
                pascals_triangle[level - 1][column];
        }
    }

    return pascals_triangle;
}

main.c:

#include "pascals_triangle.h"
#include <stdlib.h>
#include <stdio.h>

int main()
{
    int* returnColumnSizes;
    int returnSize;

    int** rows = generate(5, &returnSize, &returnColumnSizes);

    for (size_t level = 0; level < returnSize; level++)
    {
        for (size_t column = 0; column <= level; column++)
        {
            printf("%d ", rows[level][column]);
        }

        free(rows[level]);
        puts("");
    }

    free(rows);
    return EXIT_SUCCESS;
}

Hope that helps.