C solution to Leetcode "Two Sums" has runtime error

Question

I just finished my C solution of Leetcode "Two Sums". But the website says "Runtime Error", without saying which line of code is wrong. The following code runs perfectly in Xcode. Is there anything wrong with my code?

int* twoSum(int* nums, int numsSize, int target);

int main(int argc, const char * argv[]) {
    int nums[] = { 1, 2, 4, 8, 16};
    int numsSize = 5;
    int target = 10;
    int *answer = twoSum(nums, numsSize, target);

    printf("index1 = %d, index2 = %d\n", answer[0], answer[1]);

    return 0;
}

struct bucketLayer {
    int data;
    int index;
    struct bucketLayer* ptr;
};

struct result {
    int found;
    int index;
};

struct bucketLayer *addData(int data, int index, struct bucketLayer *targetPtr);
struct result findData(int data, int firstIndex, struct bucketLayer *targetPtr);
struct bucketLayer *freeBucket(struct bucketLayer *bucketPtr);

int* twoSum(int* nums, int numsSize, int target) {
    struct bucketLayer *buckets[target];

    int *answer = (int *)malloc(2 * sizeof(int));

    for (int i = 0; i < numsSize; i++) {
        buckets[nums[i] % target] = addData(nums[i], i, buckets[nums[i] % target]);
    }

    for (int i = 0; i < numsSize - 1; i++) {
        struct result findResult = findData(target - nums[i], i, buckets[target - nums[i] % target]);
        if (findResult.found) {
            if (findResult.index > i) {
                answer[0] = i+1;
                answer[1] = findResult.index + 1;
                return answer;
            } else {
                answer[0] = findResult.index + 1;
                answer[1] = i + 1;
                return answer;
            }
        }
    }

    for (int i = 0; i < target; i++) {
        buckets[i] = freeBucket(buckets[i]);
    }

    return answer;
}

struct bucketLayer *addData(int data, int index, struct bucketLayer *targetPtr) {
    if (targetPtr == NULL) {
        targetPtr = (struct bucketLayer *)malloc(sizeof(struct bucketLayer));
        targetPtr->data = data;
        targetPtr->index = index;
        targetPtr->ptr = NULL;
    } else {
        targetPtr->ptr = addData(data, index, targetPtr->ptr);
    }

    return targetPtr;
}

struct result findData(int data, int firstIndex, struct bucketLayer *targetPtr) {
    struct result findResult;
    if (targetPtr == NULL) {
        findResult.found = 0;
        return findResult;
    } else {
        if (targetPtr->data == data && targetPtr->index != firstIndex) {
            findResult.found = 1;
            findResult.index = targetPtr->index;
            return findResult;
        } else {
            return findData(data, firstIndex, targetPtr->ptr);
        }
    }
}

struct bucketLayer *freeBucket(struct bucketLayer *bucketPtr) {
    if (bucketPtr != NULL) {
        bucketPtr->ptr = freeBucket(bucketPtr->ptr);
        free(bucketPtr);
    }
    return bucketPtr;
}

TL;DR This is not a code review site. If you have a specific question, please show what you have done. However, a hint: _undefined behaviour_ is well known to behave different on different systems. I'd check for this. — too honest for this site, Jul 05 '15 at 03:45
Standard warning: do not cast `void *` as returned by `malloc`. — too honest for this site, Jul 05 '15 at 03:46
@Olaf Thanks. You mean I should remove explicit pointer cast from malloc? The K&R C textbook use this style. And even I remove the explicit cast, leetcode.com still gives me runtime error. — Zhu Shengqi, Jul 05 '15 at 04:38
Guess: `buckets` is a local variable, and not zero-initialized. So `targetPtr` in `addData` is garbage and testing it against `NULL` have no sense. — , Jul 05 '15 at 04:39
@deniss Thanks a lot! You are correct, in my Xcode the pointers are automatically initialized with zero, but Leetcode.com seems to use gcc. — Zhu Shengqi, Jul 05 '15 at 04:49
Hint: While K&R has been a excellent book for its time, this time is over since more than 20 years: Better use a book that's more recent than 1988. — Daniel Jour, Jul 05 '15 at 05:24
@DanielJour You are right. I'm trying to find a newer version of c textbook. Maybe C Primer Plus is a good choice? — Zhu Shengqi, Jul 05 '15 at 05:42
Do you know about this list? http://stackoverflow.com/q/562303/1116364 — Daniel Jour, Jul 05 '15 at 06:23
I strongly recomend to get a more recent C book than K&R. The examples might be ok for a try, but the language itself has very much evolved with C99. Some of its recomendations have been superseded for good reasons. Read [here](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — too honest for this site, Jul 05 '15 at 14:35
@DanielJour: I agree about K&R's book being outdated, but IIRC, they provided a more recent version which at least covers ANSI-C (C89/C90). — too honest for this site, Jul 05 '15 at 14:37
@Olaf yes, that's the 1988 version I was referring to. The previous, first edition is from 1978. — Daniel Jour, Jul 05 '15 at 18:51
@DanielJour: Yes, I have the first Ed. in mybookshelf. Tried to learn C with that, got confused with types and started with Modula-2 happily for years - loong time ago. — too honest for this site, Jul 05 '15 at 20:32

David C. Rankin · Accepted Answer · 2015-07-05T06:34:15.960

After a closer look at the code, the problem is introduced by the use of the variable length array of pointers to struct bucketLayer. In that instance while there is a static pointer available, the pointer is uninitialized and causes the addData function to incorrectly handle the pointer. Manual initialization is all that is needed:

struct bucketLayer *buckets[target];

for (int i = 0; i < target; i++)
    buckets[i] = NULL;

int *answer = malloc (2 * sizeof *answer);

for (int i = 0; i < numsSize; i++) {
    buckets[nums[i] % target] = addData(nums[i], i, buckets[nums[i] % target]);
}

The addData allocation can also be reduced to:

 targetPtr = malloc (sizeof *targetPtr);

@DavidC.Rankin Thanks. By the way, if buckets is allocated after it's declared, my addData() would not work. addDatda() do the job of checking and allocating memory :) — Zhu Shengqi, Jul 05 '15 at 06:12

C solution to Leetcode "Two Sums" has runtime error

1 Answers1