CODEWITHSUNDEEP
arraysccomparison-operatorsset-intersection
user15112440
user15112440

Reputation:

Why is this below code giving heap overflow Error by just changing the comparison operator from &&(AND) to ||(OR)?

I was trying to solve below problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

Here is my code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    
    for(int i=0; i<nums1Size-1; i++){
        if(nums1[i]>nums1[i+1]){
            int temp = nums1[i];
            nums1[i] = nums1[i+1];
            nums1[i+1] = temp;
            i = -1;
        }
    }
    
    for(int i=0; i<nums2Size-1; i++){
        if(nums2[i]>nums2[i+1]){
            int temp = nums2[i];
            nums2[i] = nums2[i+1];
            nums2[i+1] = temp;
            i = -1;
        }
    }
    
    int i = 0;
    int j = 0;
    int* res = (int*)malloc(10* sizeof(int));
    int k = 0;
    
    if(!(nums1Size > nums2Size)){
        int * temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        int tempint = nums1Size;
        nums1Size = nums2Size;
        nums2Size = tempint;
    }
    
    while(i<nums1Size && j<nums2Size){
        if(nums1[i] > nums2[j]){
            j++;
        }
        else if(nums1[i] < nums2[j]){
            i++;
        }
        else{
            res[k++] = nums1[i];
            i++; j++;
        }
    }
    *returnSize = sizeof(res)/sizeof(res[0]);
    return res;

}

Upvotes: 0

Views: 102

Answers (1)

Luca Polito
Luca Polito

Reputation: 2892

To simplify the problem you have to solve, let's first write a helper function that counts the number of occurrences of a particular element inside an array:

int count_elem(int* arr, int n, int elem) {
    int count = 0;

    for (int i = 0; i < n; i += 1) {
        if (arr[i] == elem) {
            count += 1;
        }
    }

    return count;
}

Now, let's try to solve the problem following the problem description:

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // here we allocate `res` with size of the biggest array, because that's the worst case we'll have
    int* res = malloc(sizeof(int) * ((nums1Size > nums2Size) ? nums1Size : nums2Size));

    // just to be sure `malloc()` did not return an error
    if (res == NULL) {
        return NULL;
    }

    // we'll keep track of how many elements we actually put inside `res`
    *returnSize = 0;

    // let's loop through all elements of `nums1`
    for (int i = 0; i < nums1Size; i += 1) {
        int elem = nums1[i];

        // if we already put the element inside `res`, we skip this cycle
        int count_res = count_elem(res, *returnSize, elem);
        if (count_res > 0) {
            continue;
        }

        // let's count the occurrences in both arrays
        int count1 = count_elem(nums1, nums1Size, elem);
        int count2 = count_elem(nums2, nums2Size, elem);

        // let's calculate how many times the element must be present inside `res`
        // i.e.: the same number of times of the array with the fewer occurrences of it
        // NOTE: if `nums1` or `nums2` do not include the element, we also don't include it inside `res`
        int count_min = (count1 < count2) ? count1 : count2;

        // now let's put inside `res` as many times as we previously calculated
        for (int i = 0; i < count_min; i += 1) {
            res[*returnSize] = elem;
            *returnSize += 1;
        }
    }

    return res;
}

Let's try if it works:

int main(void) {
    int arr1[] = {1, 2, 2, 1};
    int arr2[] = {2, 2};

    int res_size;
    int* res = intersect(arr1, sizeof(arr1) / sizeof(arr1[0]), arr2, sizeof(arr2) / sizeof(arr2[0]), &res_size);

    // let's print the result of `intersect()`
    for (int i = 0; i < res_size; i += 1) {
        printf("%d\n", res[i]);
    }

    return 0;
}

Output:

2
2

NOTE: the function is not optimized for speed nor for memory efficiency. This will be left as an exercise for the reader.

UPDATE

The previous version of the answer was wrong (sorry again). Now it should be correct.

Upvotes: 0

Related Questions