Find four,whose sum equals to target

Question

Problem:
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
-109 <= nums[i] <= 109
-109 <= target <= 109

Algorithm:

1. First we sort an array;
2. Pick three different numbers;
3. Find fourth number, which has to equal to target - num1 - num2 - num3

.

C code:

int partition (int *arr, int left, int right) {
    int x = arr[right];
    int i, j;
    i = left - 1;
    for (j = left; j < right; j++)
        if (arr[j] <= x) {
            int tmp = arr[++i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    arr[right] = arr[++i];
    arr[i] = x;
    return i;
}

void quicksort (int *arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quicksort(arr, left, pivot - 1);
        quicksort(arr, pivot + 1, right);
    }
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    (*returnSize) = 0;
    int **ans = NULL;
    quicksort(nums, 0, numsSize - 1);
    for (int i = 0; i < numsSize - 3; i++)
        for (int j = i + 1; j < numsSize - 2; j++)
            for (int k = j + 1; k < numsSize - 1; k++) {
                int l = target - nums[i] - nums[j] - nums[k];
                int left = k, mid, right = numsSize;
                while (left < right ) {
                    mid = (left + right) / 2;
                    if (nums[mid] < l)
                        left = mid;
                    else if (nums[mid] == l) {
                        (*returnSize)++;
                        ans = realloc(ans, (*returnSize) * sizeof(int));
                        ans[*returnSize - 1][0] = nums[i];
                        ans[*returnSize - 1][1] = nums[j];
                        ans[*returnSize - 1][2] = nums[k];
                        ans[*returnSize - 1][3] = nums[l];
                        break;
                    }
                    else
                        right = mid;
                }

            }
        *returnColumnSizes = malloc((*returnSize) * sizeof(int));
        for (int i = 0; i < (*returnSize); i++)
            (*returnColumnSizes)[i] = 4;
    return ans;
}

I thought this is quite optimal solution, but it doesn't even pass time limit.

Answer 1

Small array size allows to create storage for n*(n-1)/2 pairs (~20000) of structures, containing sum of all possible pairs and corresponding indices

Sort structures by sum value

Then for every sum S with i,j indices look for pairs with target-S and indices distinct from i,j (scan sums from the left, corresponding sums from the right)

Overall complexity is O(n^2*log(n))

(Also it is possible to use hash table, but there is no in-built hash tables in C)