dynamic array segmentation fault

Question

Here are two codes one uses 2d array and other uses pointers.
The catch is the code with pointers runs fine and the other with 2d array gives segmentation fault in some test cases(not all). It passes all testcases n<=1000 .

Limit of n is 1< n <10000.

The logic of both code are correct.
Problem: https://www.hackerrank.com/challenges/dynamic-array/problem

I need to know why the use of 2d array is giving segmentation fault. Is it bad to use 2d array and use pointers instead. But both are same things.

This is the code which gives segmentation fault

int main()
{

    /* Enter your code here. Read input from STDIn. Print output to STDOUT */
    int n, q, o, x, y, ti, pi, la, j;

    scanf("%d%d",&n,&q);
    int v[n][n],a[n];

    for (j = 0; j<n; j++)
        a[j] = 0;

    la=0;
    while(q-->0)
    {
        scanf("%d%d%d",&o,&x,&y);
        ti=((x^la)%n);
        switch(o)
        {
        case 1:
            v[ti][a[ti]]=y;
            a[ti]++;
            break;

        case 2:
            pi = y % a[ti];
            printf("%d\n", v[ti][pi]);
            la = v[ti][pi];

            break;
        }
    }
    return 0;
}

This code run fine

int main()
{
    int n, q, o, x, y, ti, pi, la;
    int *a, *s;
    int **v;
    scanf("%d %d", &n, &q);
    v = (int **)malloc(n * sizeof(int *));
    a = (int *)malloc(n * sizeof(int));
    s = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
    {
        s[i] = 1;
        v[i] = (int *)malloc(s[i] * sizeof(int));
        a[i] = 0;
    }
    la = 0;
    for (int i = 0; i < q; i++)
    {
        scanf("%d %d %d", &o, &x, &y);
        ti = (x ^ la) % n;
        if (o == 1)
        {
            v[ti][a[ti]] = y;
            a[ti] ++;
            if (a[ti] == s[ti])
            {
                 s[ti] *= 2;
                v[ti] = realloc(v[ti], s[ti] * sizeof(int));
            }
        }
        else
        {
            pi = y % a[ti];
            printf("%d\n", v[ti][pi]);
            la = v[ti][pi];
        }
    }
    free(s);
    free(a);
    free(v);
    return 0;
}

THE TEST CASES ARE AS FOLLOWS

n=99999 q=99977
1 624371833 212297989
1 93347849 234235833
1 683498501 669278504
1 364574347 423183716
continues..

view full testcase here

http://www.writeurl.com/text/z2qlksiktbd7aeuvy3zj/dvgaqxcmeugthbkutrtn

Please provide sample input that results in the segfault. The code is pretty much identical in both. Typically the problem in the first case is that VLAs are implemented by your compiler in such a way that they cannot be too large, else it will cause an issue. One possible resolution is to change the compiler setting for the stack size, but this is not necessarily the correct solution for you. — , Sep 26 '17 at 01:12
actually this is competitive programming problem on hackerrank so there is not really much I can do. I will provide you with the test case but currentlry hackerrank seems to be down with some technical error. — wehadarar, Sep 26 '17 at 01:23
`sizeof v == 99999 * 99999 * sizeof(int)` in the 2D array case, which results in `9999800001 * sizeof(int)`. That's a very large amount of memory to allocate on the stack, which is likely the source of your segfault. Since the other implementation doesn't have the issue, use it instead, and good luck solving the challenge if you haven't already! :) — , Sep 26 '17 at 02:40
@wehadarar - I think you answered your own question in your first comment. See [**C/C++ maximum stack size of program**](https://stackoverflow.com/questions/1825964/c-c-maximum-stack-size-of-program) — David C. Rankin, Sep 26 '17 at 05:23

dynamic array segmentation fault

0 Answers0