LeetCode //C - 18. 4Sum

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.
 

Example 1:

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

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• $-10^9<=nums[i]<=10^9$
• $-10^9<=target<=10^9$

From: LeetCode
Link: 18. 4Sum

Solution:

Ideas:

1. Sorting: The array is sorted to allow efficient searching and to easily skip duplicates.
2. Nested Loops with Two-pointer Technique: The function uses a nested loop for the first two elements of the quadruplet and then applies the two-pointer approach for the remaining two elements.
3. Avoiding Duplicates: To ensure all quadruplets are unique, the function skips over duplicate elements, similar to the approach used in 3Sum.
4. Memory Management: The function initializes with a set capacity for result storage, reallocating as necessary. This needs careful handling to avoid memory leaks. Users of this function must free the memory allocated for each quadruplet as well as the result array and column sizes array.

Code:

// Comparator function for qsort
int compare(const void *a, const void *b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);
    return int_a > int_b ? 1 : int_a < int_b ? -1 : 0;
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);
    *returnSize = 0;
    int capacity = 500;  // Adjust this capacity according to the expected number of results
    int** result = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));

    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // skip duplicates

        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;  // skip duplicates

            int left = j + 1;
            int right = numsSize - 1;

            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; // use long long to prevent overflow
                if (sum == target) {
                    // Save the quadruplet
                    if (*returnSize == capacity) {
                        // Increase capacity if needed
                        capacity *= 2;
                        result = (int**)realloc(result, capacity * sizeof(int*));
                        *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
                    }
                    result[*returnSize] = (int*)malloc(4 * sizeof(int));
                    result[*returnSize][0] = nums[i];
                    result[*returnSize][1] = nums[j];
                    result[*returnSize][2] = nums[left];
                    result[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;

                    // Skip duplicates
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }

    return result;
}