Zhu Shengqi
Zhu Shengqi

Reputation: 3792

C solution to Leetcode "Two Sums" has runtime error

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

Upvotes: 0

Views: 2403

Answers (1)

David C. Rankin
David C. Rankin

Reputation: 84531

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

Upvotes: 1

Related Questions