# Reimplement the top-voted java code in C (6ms)

The idea is quite simple but the coding part is kind of complicated when you use C because you need to write `sort` and `dynamic array` by hand, which is the major purpose of this post.

``````/* Here we implement the quick sort algorithm. */
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *arr, int left, int right) {
int pi = left;
for (int i = left; i < right; ++i) {
if (arr[i] <= arr[right])
swap(&arr[pi++], &arr[i]);
}
swap(&arr[pi], &arr[right]);
return pi;
}
void quick_sort(int *arr, int left, int right) {
if (left >= right) return;
int pi = partition(arr, left, right);
quick_sort(arr, left, pi-1);
quick_sort(arr, pi+1, right);
}

/* Here we implement the logic to double size a 2-D array. */
void check_size(int ***rets_ref, int *curr_size, int *max_size) {
// we need to pass 2-D array as (int ***) to modify in place.
if (*curr_size < *max_size) return;
*max_size *= 2; // double size
int **rets = malloc(sizeof(int *)*(*max_size));
for (int i = 0; i < *curr_size; ++i) {
rets[i] = (*rets_ref)[i];
}
int **tmp = *rets_ref;
*rets_ref = rets;
free(tmp);
}

/* Here we implement the 2-sum, 3-sum and 4-sum logic. */
void twoSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1, int z2) {
int **rets;
int i = pi, j = numsSize-1, sum, x;
while (i < j) {
sum = nums[i] + nums[j];
if (sum == target) {
rets = *rets_ref; // may be resized during iteration
rets[*returnSize] = malloc(sizeof(int)*4);
rets[*returnSize][0] = z1;
rets[*returnSize][1] = z2;
rets[*returnSize][2] = nums[i];
rets[*returnSize][3] = nums[j];
(*returnSize)++;
check_size(rets_ref, returnSize, size); // check and resize
x = nums[i];
while(++i < j && x == nums[i]); //avoid duplicate
x = nums[j];
while(--j > i && x == nums[j]); //avoid duplicate
} else if (sum < target) {
i++;
} else {
j--;
}
}
}
void threeSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1) {
int **rets;
for (int i = pi; i < numsSize; ++i) {
if (i >= numsSize-2)
break; //no more
if (i > pi && nums[i] == nums[i-1])
continue; //avoid duplicate
if (nums[i]+2*nums[numsSize-1] < target)
continue; //too small
if (3*nums[i] > target)
break; //to large
if (3*nums[i] == target) {
rets = *rets_ref;
if (i+2 < numsSize && nums[i+2] == nums[i]) {
rets[*returnSize] = malloc(sizeof(int)*4);
rets[*returnSize][0] = z1;
for (int j = 0; j < 3; ++j)
rets[*returnSize][j+1] = nums[i+j];
(*returnSize)++;
check_size(rets_ref, returnSize, size); // check and resize
}
break;
}
twoSum(nums, numsSize, target-nums[i], i+1, rets_ref, returnSize, size, z1, nums[i]);
}
}
int** fourSum(int *nums, int numsSize, int target, int *returnSize) {
int **rets;
int size = numsSize;
rets = malloc(sizeof(int *)*size);
*returnSize = 0;
quick_sort(nums, 0, numsSize-1);
for (int i = 0; i < numsSize; ++i) {
if (i >= numsSize-3)
break; //no more
if (i && nums[i] == nums[i-1])
continue; //skip duplicate
if (nums[i]+3*nums[numsSize-1] < target)
continue; //too small
if (4*nums[i] > target)
break; //to large
if (4*nums[i] == target) {
if (i+3 < numsSize && nums[i+3] == nums[i]) {
rets[*returnSize] = malloc(sizeof(int)*4);
for (int j = 0; j < 4; ++j)
rets[*returnSize][j] = nums[i+j];
(*returnSize)++;
check_size(&rets, returnSize, &size); // check and resize
}
break;
}
threeSum(nums, numsSize, target-nums[i], i+1, &rets, returnSize, &size, nums[i]);
}
return rets;
}
``````

It will be more elegant to implement a dynamic array and some methods.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.