# C solution with quick sort.

• First we need to sort the two arrays. The rest will be very easy.

``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int partition(int*a, int l, int r) {
int x = a[l];
while(l < r) {
while(a[r] > x && l < r) --r;
if(l < r) {
a[l] = a[r];
++l;
}
while(a[l] < x && l < r) ++l;
if(l < r) {
a[r] = a[l];
--r;
}
}
a[l] = x;
return l;
}

void quick_sort(int* a, int l, int r) {
if(l < r) {
int m = partition(a, l, r);
quick_sort(a, l, m-1);
quick_sort(a, m+1, r);
}
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
quick_sort(nums1, 0, nums1Size-1);
quick_sort(nums2, 0, nums2Size-1);
int* result = (int*)malloc((nums1Size > nums2Size ? nums1Size : nums2Size) * sizeof(int));
int i = 0, j = 0;
*returnSize = 0;
while(i < nums1Size && j < nums2Size) {
if(nums1[i] == nums2[j]) {
if(*returnSize > 0 && result[(*returnSize)-1] != nums1[i])
result[(*returnSize)++] = nums1[i];
else if(0 == *returnSize)
result[(*returnSize)++] = nums1[i];
++i;
++j;
}
else if(nums1[i] > nums2[j]) ++j;
else ++i;
}
return result;
}
``````

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