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

Answer 1

_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".

Answer 2

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);
}

Answer 3

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];
            ^^^