Variable sized array in C

Question

For some reason, the first output my program is giving, is garbage value, while the second output is correct.

This is a problem from HackerRank.

I know this question has already been asked by someone else. I just want to know what the problem is in my code.

#include <stdio.h>

int main()
{
    int index,query;
    int count1 = 0;
    scanf("%d%d",&index,&query);
    for(int i=0;i<index;i++)
    {
        int b;
        scanf("%d",&b);
        int A[index][b];
        for(int j=0;j<b;j++)
        {
            scanf("%d",&A[i][j]);
        }
        count1++;
        if(count1<index)
        {
            continue;
        }
        int count2=0;
        while(count2<query)
        {
            int d,e;
            scanf("%d%d",&d,&e);
            printf("%d\n",A[d][e]);
            count2++;
        }
    }
    return 0;
}

If the input is:

2 2
3 1 5 4
5 1 2 8 9 3
0 1
1 3

Then the output should be:

5
9

But instead, my output is:

garbage
9

Your code could really benefit from meaningful variable names. — Eugene Sh.
– Eugene Sh., Commented Jul 24, 2019 at 16:54
@ChrisTurner OP is renaming their variables... in progress . . — gsamaras
– gsamaras, Commented Jul 24, 2019 at 17:02
Sorry, but your code is not close to a solution to the problem. The input starts with two numbers, the number of arrays n and the number of queries q. So first you have to read those. (I see you are making edits and appear to be using index for n and query for q. You might do better either to stick to the names in the problem or to use more descriptive names like NumberOfArrays instead of index.) Then the input has n lines, each with some number of values. So your program needs to read each of those lines… — Eric Postpischil
– Eric Postpischil, Commented Jul 24, 2019 at 17:05
@ToninGuy3n I feel empathy for you. Variable Length Array became legal with C99. — gsamaras
– gsamaras, Commented Jul 24, 2019 at 17:57

gsamaras · Accepted Answer · 2019-07-24 18:32:20Z

_Disclaimer

_{I didn't even click the link, so I do not know if the solution is correct, but assuming that you got the logic right..}

The problem

is that you populate in stages a local to the body of the for loop 2D array, which at the end of your processing, you expect to have it accessible (I mean the complete matrix, populated from every single iteration of the for loop).

Instead, you get only the last's iteration declared array, that's why you get only the A[1][3] element right, and not the A[0][1], since the 2nd row is populated in the last (2nd iteration), while the 1st row is populated in the first iteration (of the firstly declared A), which goes out of scope as soon as the first iteration terminates.

The fix

So, what you need to fix this is to dynamically allocate memory for your matrix, and every time a new dimension for the columns is inputed, resize it with realloc().

I believe that the explanation I have in 2D dynamic array (C) will help you, since what you want is the number of rows fixed, and the number of columns adjustable on every iteration.

Below is an illustration based on the link I shared above, which visualizes what exactly is your matrix (a 1D array of pointers), and shows how the code below manipulates it:

Full code example:

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

int main()
{
    int index,query;
    int count1 = 0;
    scanf("%d%d",&index,&query);

    // An array of `index` (e.g. 2) pointers to integers
    int *A[index];
    // Initialize all the pointers to NULL
    for(int k = 0; k < index; ++k)
      A[k] = NULL;

    for(int i=0;i<index;i++)
    {
        int b;
        scanf("%d",&b);

        // Replaced your 'int A[index][b];' with the following:
        // Every time a new number of columns (that's 'b') is read,
        // we need to adjust the numbers of columns our matrix ('A') has.
        // That means, that for every pointer (row), we need to re-allocate
        // the number of columns it points to, which is basically a 1D array, of dimension 'b'
        for(int k = 0; k < index; ++k)
          A[k] = realloc(A[k], b * sizeof(int) );

        for(int j=0;j<b;j++)
        {
            scanf("%d",&A[i][j]);
        }
        count1 ++;
        if(count1<index)
        {
            continue;
        }
        int count2=0;
        while(count2<query)
        {
            int d,e;
            scanf("%d%d",&d,&e);
            printf("%d\n",A[d][e]);
            count2++;
        }
    }

    // Free the dynamically allocated memory
    for(int k = 0; k < index; ++k)
          free(A[k]);
    return 0;
}

Output (for the input provided):

5
9

Pro-tip: The typical methodology of calling realloc() is to use a specific pointer for the reallocation, test that pointer and, if everything worked out ok, change the old pointer, as explained in Does realloc overwrite old contents?, which I didn't do in that post for the sake of being "laconic".

Vlad from Moscow · Accepted Answer · 2019-07-24 17:28:54Z

The C VLA is not suitable here. It seems you need to allocate memory dynamically. The only VLA that can be used is an array of pointers to other arrays. All other arrays should be allocated dynamically.

Something like the following.

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

int main( void ) 
{
    size_t number_of_arrays;
    size_t number_of_queries;

    scanf( "%zu%zu", &number_of_arrays, &number_of_queries );

    int **a = malloc( number_of_arrays * sizeof( int * ) );

    for ( size_t i = 0; i < number_of_arrays; i++ )
    {
        size_t size;
        scanf( "%zu", &size );

        a[i] = malloc( size * sizeof( int ) );

        for ( size_t j = 0; j < size; j++ ) scanf( "%d", &a[i][j] );
    }

    for ( size_t i = 0; i < number_of_queries; i++ )
    {
        size_t array_index;
        size_t element_index;

        scanf( "%zu%zu", &array_index, &element_index );

        printf( "%d\n", a[array_index][element_index] );
    }

    for ( size_t i = 0; i < number_of_arrays; i++ ) free( a[i] );
    free( a );                                                         
}

If to input

2 2
3 1 5 4
5 1 2 8 9 3
0 1
1 3

then the program output will be

5
9

As for your code then it is invalid. For example the variable b is not initialized so the declaration of the array has undefined behavior.

int b;
scanf("%d",&b);
int A[index][b];
            ^^^

gsamaras · Accepted Answer · 2019-07-24 18:48:07Z

1

Hint : Variable sized arrays need to be dynamically allocated, here's how to it in C

int rows; 
scanf("%d",&rows);

//2D array 
int**A = malloc(sizeof(int*)*rows); //allocate number of rows

//for each row allocate number of colums 
for(int i = 0; i < rows; i++)
{
   int cols;
   scanf("%d",&cols);
   A[i] = malloc(sizeof(int)*cols);
}

edited Jul 24, 2019 at 18:48

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

answered Jul 24, 2019 at 17:09

Midnight Exigent

6254 silver badges20 bronze badges

4 Comments

ToninGuy3n Over a year ago

OP isn't asking for code solution. They're asking for an explanation on what they did wrong.

Midnight Exigent Over a year ago

I did not give the solution, as what he did wrong was explained by someone else, this is supposed to be a hint on how to solve the problem.

gsamaras Over a year ago

Hi @WalidJabari probably by other you mean me! :) I updated my answer with a fix BTW.. I understand your intention for your hint, but notice that Variable Length Array became legal with C99.

Midnight Exigent Over a year ago

Hi @gsamaras indeed, I just read your updated answer. Although VLA are legal, some compilers (like MSVC) will not allow something like int n = 5; int arr[n]; I personally prefer to stay away from VLA

Collectives™ on Stack Overflow

Variable sized array in C

3 Answers 3

_Disclaimer

The problem

The fix

Comments

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Disclaimer

The problem

The fix

Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related

_Disclaimer