# [C] 4ms O(n log n) solution

• I guess this would be way easier with C++ using standard container and standard algorithms, but here you go, intersection using quicksort [O(n log n)] and linear set exploration [O(n)].

There is an additional memory use but I needed it to avoid side effects of the code.

``````void swap(int *src, int *dst) {
int tmp = *src;
*src = *dst;
*dst = tmp;
}

void quick_sort(int* unsorted, int low, int high) {
if ((high - low) > 0) {
int pivot = high;
int lower_check = low;
while (lower_check < pivot) {
if ((pivot - lower_check) > 1) {
if (unsorted[lower_check] > unsorted[pivot]) {
swap(&unsorted[pivot], &unsorted[pivot - 1]);
swap(&unsorted[lower_check], &unsorted[pivot]);
--pivot;
} else {
++lower_check;
}
} else {
if (unsorted[lower_check] > unsorted[pivot]) {
swap(&unsorted[lower_check], &unsorted[pivot]);
--pivot;
}

break;
}
}
quick_sort(unsorted, low, pivot - 1);
quick_sort(unsorted, pivot + 1, high);
}
}

/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int minSize;

if (nums1Size <= nums2Size) {
minSize = nums1Size;
} else {
minSize = nums2Size;
}

int *result = (int*)calloc(minSize, sizeof(int));

int *tmp1 = (int*)calloc(nums1Size, sizeof(int));
memcpy(tmp1, nums1, sizeof(int)*nums1Size);

int *tmp2 = (int*)calloc(nums2Size, sizeof(int));
memcpy(tmp2, nums2, sizeof(int)*nums2Size);

quick_sort(tmp1, 0, nums1Size-1);
quick_sort(tmp2, 0, nums2Size-1);

int last_tmp1_value = tmp1[0];
int last_tmp2_value = tmp2[0];
int intersect_location = 0;

int tmp1_loc = 0;
int tmp2_loc = 0;
while ((tmp1_loc < nums1Size) && (tmp2_loc < nums2Size)) {
if (last_tmp1_value == last_tmp2_value) {
result[intersect_location] = last_tmp1_value;
++intersect_location;

while((tmp1[tmp1_loc] == last_tmp1_value) && (tmp1_loc < nums1Size)) {
++tmp1_loc;
}

last_tmp1_value = tmp1[tmp1_loc];

while((tmp2[tmp2_loc] == last_tmp2_value) && (tmp2_loc < nums2Size)) {
++tmp2_loc;
}

last_tmp2_value = tmp2[tmp2_loc];

} else if (last_tmp1_value < last_tmp2_value) {
while((tmp1[tmp1_loc] == last_tmp1_value) && (tmp1_loc < nums1Size)) {
++tmp1_loc;
}

last_tmp1_value = tmp1[tmp1_loc];
} else {
while((tmp2[tmp2_loc] == last_tmp2_value) && (tmp2_loc < nums2Size)) {
++tmp2_loc;
}

last_tmp2_value = tmp2[tmp2_loc];
}
}

*returnSize = intersect_location;
return result;
}
``````

I suppose this could be made prettier, but I want to work on something else ;)

• @Jazzinghen Standard c supports qsort algorithms. Here is my solution, 4ms.

``````int cmp(const void *a, const void *b) {
int arg1 = *(const int *)a;
int arg2 = *(const int *)b;

if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;

return 0;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int i, j;
int resultSize = nums1Size < nums2Size ? nums1Size : nums2Size;
int *returnNums = (int *)malloc(resultSize * sizeof(int));
int *found;

qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);

for (i = 0, j = 0; i < nums2Size; i++) {
found = bsearch(&nums2[i], nums1, nums1Size, sizeof(int), cmp);
if (found) {
if (NULL == bsearch((int *)found, returnNums, j, sizeof(int), cmp))
returnNums[j++] = *(int *)found;
}
}
returnNums[j] = '\0';
*returnSize = j;

return returnNums;
}
``````

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