# C solution using sets 13ms

• ``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/

// can be redifined for any item
typedef int item;

typedef struct set
{
int size;
item * elements; // pointer to item array allocated later
} set;

set * make_set(item arr[], int size);
bool is_set_empty(set * st);
bool is_member(set * st, item itm);
void free_set(set * st);

int * intersection(int * nums1, int nums1Size, int * nums2, int nums2Size, int * returnSize)
{
/* makes the two arrays into two sets and returns the common elements of the sets */
int i, j;
int * ret_array, ret_size;
set * nums1_set, * nums2_set, * smaller_set, * bigger_set;

// create the sets
nums1_set = make_set(nums1, nums1Size);
nums2_set = make_set(nums2, nums2Size);

// if sets are empty go home
if (is_set_empty(nums1_set) || is_set_empty(nums2_set))
return NULL;

// find out which one is smaller and which one is bigger
if (nums1_set->size < nums2_set->size)
{
smaller_set = nums1_set;
bigger_set = nums2_set;
}
else
{
smaller_set = nums2_set;
bigger_set = nums1_set;
}
// if they are equal it doesn't matter which is which

// create the return array with the size of the smaller set
if ( (ret_array = malloc(smaller_set->size * sizeof(*ret_array)) ) == NULL)
exit(EXIT_FAILURE);

// fill in only elements common for the two sets and count how many they are
for (i = ret_size = 0; i < smaller_set->size; ++i)
for (j = 0; j < bigger_set->size; ++j)
if (smaller_set->elements[i] == bigger_set->elements[j])
{
ret_array[ret_size++] = smaller_set->elements[i];
break;
}

free_set(nums1_set);
free_set(nums2_set);

// return the number of common elements and a pointer to the first one
*returnSize = ret_size;
return ret_array;
}

set * make_set(item arr[], int size)
{
/* allocates memory and extracts only
* elements which do not repeat */
int i, j;
bool is_in_set;
set * new_set;

// go home if nothing to do
if (size < 1)
return NULL;

if ( (new_set = malloc(sizeof(*new_set)) ) == NULL)
exit(EXIT_FAILURE);

new_set->size = 0;
if ( (new_set->elements = malloc(size * sizeof(item)) ) == NULL)
exit(EXIT_FAILURE);

// put in first element
new_set->elements[0] = arr[0];
++new_set->size;

// get all other unique elements
for (i = 1; i < size; ++i)
{
is_in_set = false;
for (j = 0; j < new_set->size; ++j)
{
if (arr[i] == new_set->elements[j])
{
is_in_set = true;
break;
}
}

if (!is_in_set)
new_set->elements[new_set->size++] = arr[i];
}

return new_set;
}

bool is_set_empty(set * st)
{
/* checks if set is empty */
return (st == NULL) ? true : false;
}

bool is_member(set * st, item itm)
{
/* checks if the item exists in the set */
int i;

for (i = 0; i < st->size; ++i)
if (i == st->elements[i])
return true;

return false;
}

void free_set(set * st)
{
/* frees set memory */
free(st->elements);
free(st);
}
``````

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