Solution in C for Intersection of Two Arrays II [Leetcode]

Intuition

We sort the arrays and find the common elements between the two

Approach

We first sort both arrays using quicksort and then proceed to match the elements which are same in both arrays. We update the old array(to reduce space complexity) and also update the returnSize pointer so that the required protion of the returned array is accepted for answer.

In case you’re wondering what is the cmp function for, it is there for the qsort function which requires a function to compare two values for it.

Complexity

• Time complexity:
  O(nlogn)
• Space complexity:
  O(n)

Code

int cmp(const void *a, const void *b)
 {
     return (*(int*)a-*(int*)b);
 }
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    int i=0, j=0, count=0;
    while (i<nums1Size && j<nums2Size)
    {
        if (nums1[i]>nums2[j]) j++;
        else if (nums1[i]<nums2[j]) i++;
        
        else if(nums1[i]==nums2[j])
        {
            nums1[count] = nums1[i];
            count++;
            i++;
            j++;
        }
    }
    *returnSize = count;
    return nums1;
}