LeetCode: 3Sum, Getting AddressSanitizer:DEADLYSIGNAL Error

Question

I tried this problem on my PC in Eclipse, and it is working fine. But, it is crashing when I am trying it in LeetCode and I don't understand why.

I am getting the error "AddressSanitizer:DEADLYSIGNAL" on LeetCode. And I can not debug it on the site, because I do not have a premium account.

In the problem, I am asked to find a solution for:

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets.

Here is my code:

 #include "common.h"


int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *returnColumnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
    int ii;
    bubble_sort(nums, numsSize);
    int **arr = (int**) calloc(numsSize* 3, sizeof(int*));
//  for (ii = 0; ii < numsSize; ii++)
//      arr[ii] =  (int*) calloc(3, sizeof(int));
    *returnSize = 0;
    int i, low, high = 0;
    int sum = 0;
    int target = 0;

    for  (i = 0; nums[i] <= 0 && i < numsSize -2;) {
        low = i + 1;
        high = numsSize - 1;

        while ( low < high) {
            sum = nums[i] + nums[low] + nums[high];
            if (sum > target)
                high--;
            else if (sum < target)
                low++;
            else {
                *returnSize += 1;
                arr[*returnSize-1] = (int*)malloc(sizeof(int)*3);
                arr[*returnSize-1][0] = nums[i];
                arr[*returnSize-1][1] = nums[low];
                arr[*returnSize-1][2] = nums[high];
                do high--; while(nums[high] == nums[high+1] && low < high);
            }

        }
        do i++; while (nums[i]==nums[i-1] && i < numsSize-2);
    }

    return arr;
}

void run_3sum() {
    printf("\n ---------- Run 3Sum ----------- \n");
    int n = 8;
    int i = 0;
    int* returnSize = (int*) malloc(sizeof(int));
    int** returnColumnSizes = (int**) malloc(sizeof(int));;
    int **res;
    int arr[8] = {-10, 0, 10, 2, -2, 5, 3, -8};//{-2,0,1,2,-1,3};

    int *nums = (int*) calloc(n+4, sizeof(int));
    for (i = 0; i < n; i++) {
            *nums = arr[i];
            nums++;
        }
    nums = nums - i;
    res = threeSum(nums, n, returnSize, returnColumnSizes);
    printf("\n Results ---3sum ---\n");
    printf_3sum(res, *returnSize, 3);
}

Answer 1

There are couple of issues in your implementation. The most important reason is, you did not initialize and use int** returnColumnSizes inside the threeSum() function. You have to initialize and set values to int** returnColumnSizes. If there is no need of this variable, then leetcode should not pass this as a function parameter. Let's first understand the purpose of returnColumnSizes. Lets fist understand the function signature of threeSum:

• The function's return type is int**. Meaning, this function will return a pointer of pointers (a pointer will point to the starting pointer of an array).
• Parameter int* nums indicates the input array.
• Parameter int numsSize indicates the size of the nums array.
• Parameter int* returnSize indicates the size of the array the returning pointer points to.
• Parameter int** returnColumnSizes indicates the size of inner arrays of the returning pointer.

Here is a sample input and output form this problem:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Now, pay attention to the output. The output is an array of arrays (which is basically pointer of pointers). Now, for this output returnSize will be 2 and returnColumnSizes will be an array of size 2 and it will represent like this:

int** returnColumnSizes = [3, 3]

This represents the number of elements the inner pointers of the returning pointer is pointing to. Now as you were not setting this value inside the threeSum() function, the program raises this error as it was not sure how much it will read data from the pointer. Here I have fixed the issue:

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *returnColumnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
    int ii;
    bubble_sort(nums, numsSize);
    
    *returnSize=0;
    int **arr=(int**)malloc(sizeof(int*) * numsSize);
    *returnColumnSizes=(int*)malloc(sizeof(int) * numsSize);
    
    int i, low, high = 0;
    int sum = 0;
    int target = 0;

    for  (i = 0; nums[i] <= 0 && i < numsSize -2;) {
        low = i + 1;
        high = numsSize - 1;

        while ( low < high) {
            sum = nums[i] + nums[low] + nums[high];
            if (sum > target)
                high--;
            else if (sum < target)
                low++;
            else {
                (*returnColumnSizes)[*returnSize]=3;
                arr[*returnSize] = (int*)malloc(sizeof(int)*3);
                arr[*returnSize][0] = nums[i];
                arr[*returnSize][1] = nums[low];
                arr[*returnSize][2] = nums[high];
                (*returnSize) += 1;
                do high--; while(nums[high] == nums[high+1] && low < high);
            }
        }
        do i++; while (nums[i]==nums[i-1] && i < numsSize-2);
    }
    
    return arr;
}

There are other couple of issues in your solution as well. For example, the size of int **arr should be adjusted dynamically, otherwise it will allocate more memory than required. A general practice to handle this issue is, you should start with a lower number of memory and if needed you increase the size of this array by doubling it each time. Here you will find a more efficient solution of this problem written in C.