Dynamic Memory allocation for 2D Arrays in C Language

Question

I am trying to solve a Leetcode problem in C. https://leetcode.com/problems/pascals-triangle/description/

This is my solution to the problem. I don't think there's an issue with the solution but dynamically allocating memory for a 2D array is getting very complex. Can someone please help me figure out how to correctly allocate memory dynamically to a 2D array. Updated the code based on BLUEPIXY suggestions, I still seem to be getting runtime error.

/**
 * Return an array of arrays.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int** columnSizes) {


    int i=0,j=0,numColumns =2;

    columnSizes = (int **)malloc(numRows * sizeof(int *));
    for (i=0; i<numRows; i++)
         columnSizes[i] = (int *)malloc( sizeof(int));

    int **returnArray = (int **)malloc(numRows * sizeof(int *));
    for (i=0; i<numRows; i++)
         returnArray[i] = (int *)malloc((i+1) * sizeof(int));


    returnArray[0][0] = 1;
    *columnSizes =1;
     for(i=1;i<numRows;i++)
     {
         for(j=0;j<numColumns;j++)
        {
            if(j==0 )
               columnSizes[i][j] = returnArray[i-1][j];
            else if(j==(numColumns-1))
                columnSizes[i][j] = returnArray[i-1][j-1];
            else
                returnArray[i][j] = returnArray[i-1][j-1] + returnArray[i-1][j];

            numColumns++;
        }
        *(columnSizes+i) =  numColumns-1;
     }

    return returnArray;
}

`numColumns` needs to be changed (incremented) for each line. — BLUEPIXY, Aug 05 '17 at 05:29
Also you misunderstand the requirement specification of `generate` function. — BLUEPIXY, Aug 05 '17 at 05:49
@BLUEPIXY : Oh yes thank you, I wrote it in my notebook. Missed typing it in. Thanks for pointing it out. Although I am still getting an error. I'll try to figure what's wrong. Do you see anything wrong with the way I have allocated the memory? — CodeModeOn, Aug 05 '17 at 05:53
It worked. Thanks a Ton for the help. Been breaking my head for a while. Stupid question but I don't see an arrow against your name to give you credit and mark your comment as the solution. — CodeModeOn, Aug 05 '17 at 06:18
@BLUEPIXY - I think you will have to post it so an answer can be selected `:)` — David C. Rankin, Aug 05 '17 at 08:33
Related: [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays) — Lundin, Mar 07 '19 at 09:19

Tanuj Yadav · Answer 1 · 2017-08-05T05:18:59.693

0

Just do this

int *arr = (int *)malloc(r * c * sizeof(int));

and access the elements like this

 int i, j, count = 0;
    for (i = 0; i <  r; i++)
      for (j = 0; j < c; j++)
         *(arr + i*c + j) = ++count;

OR

If you have the pointer to the pointer, then you get get some help from this code

int main()
{
    int i,j;
    int **p;
    (p)=(int**)malloc(5*sizeof(int*));

    for(i=0;i<5;i++)
    *(p+i)=(int*)malloc(4*sizeof(int));

    for(i=0;i<5;i++)
    for(j=0;j<4;j++)
    p[i][j]=2;

    for(i=0;i<5;i++)
    for(j=0;j<4;j++)
    printf("%d",p[i][j]);
}

edited Aug 05 '17 at 05:18

answered Aug 05 '17 at 04:57

Tanuj Yadav

1,259
13
21

Hi Tanuj,Thanks for your response. I noticed the solution you provided here : http://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/ but in my case the input parameter to the function in Leetcode is a pointer to pointer. That's why I am allocating memory using a pointer to pointer, the 3rd solution in the same geeksforgeeks link. Although doesn't seem to work for me. When I return it prints out a set of null arrays. – CodeModeOn Aug 05 '17 at 05:07
Thanks for the solution. I do not see any difference between your updated method of dynamic allocation compared to my original post. I still tried inserting your solution in the Leetcode link and assigned all elements to value 2 as in your code for testing purpose. It still gives me 5 NULL arrays as output. – CodeModeOn Aug 05 '17 at 05:44
@CodeModeOn I tries your solution on the provided link, theres some problem in returning the array. And 1 thing that you are missing is, increase numColumns in the outer for loop – Tanuj Yadav Aug 05 '17 at 06:14

score 0 · Answer 2 · answered Aug 05 '17 at 05:33

If all you have to do for your programming exercise is print out the results, why bother with any storage at all? Just use the solution here.

How to efficiently calculate a row in pascal's triangle?

Regarding multi-dimensional arrays and C, there is no native support for such a thing. So you have to build your own using one or more 1-D blocks of storage and tricks to index into that storage.

The simplest thing, which @tanuj-yadav suggested works fine for most 2-d arrays is just allocate a nXm-length block of storage and do very simple index arithmetic arr[i*c+j].

The other common approach is arrays of arrays (aka ragged arrays). Which is just like a list of lists, and are naively done with a malloc on each row (or column).

score 0 · Accepted Answer · answered Aug 05 '17 at 09:04

Problems of new version

(1)

columnSizes = (int **)malloc(numRows * sizeof(int *));
for (i=0; i<numRows; i++)
    columnSizes[i] = (int *)malloc( sizeof(int));

should be

*columnSizes = malloc(numRows * sizeof(int));

(※ it is not necessary to cast from void * in C).

(2)

*columnSizes =1;//type of `*columnSizes` is `int *`

should be

**columnSizes = 1;//meant columnSizes[0] = 1; at caller side (main)

(3)

columnSizes[i][j] = returnArray[i-1][j];
...
columnSizes[i][j] = returnArray[i-1][j-1];

should be

returnArray[i][j] = returnArray[i-1][j];
...
returnArray[i][j] = returnArray[i-1][j-1];

because this is typo.

(4)

numColumns++; move to after for(j=0;j<numColumns;j++){ }

(5)

*(columnSizes+i) =  numColumns-1;

should be

*(*columnSizes+i) =  numColumns-1;//For reasons similar to (2)

The whole fix code:

int** generate(int numRows, int** columnSizes) {
    int i=0,j=0,numColumns =2;

    *columnSizes = malloc(numRows * sizeof(int));

    int **returnArray = (int **)malloc(numRows * sizeof(int *));
    for (i=0; i<numRows; i++)
         returnArray[i] = (int *)malloc((i+1) * sizeof(int));

    returnArray[0][0] = 1;
    **columnSizes = 1;
     for(i=1;i<numRows;i++)
     {
        for(j=0;j<numColumns;j++)
        {
            if(j==0 )
               returnArray[i][j] = returnArray[i-1][j];
            else if(j==(numColumns-1))
                returnArray[i][j] = returnArray[i-1][j-1];
            else
                returnArray[i][j] = returnArray[i-1][j-1] + returnArray[i-1][j];
        }
        numColumns++;
        *(*columnSizes+i) =  numColumns-1;
     }

    return returnArray;
}

Dynamic Memory allocation for 2D Arrays in C Language

3 Answers3