Find Union and Intersection of 2 sorted arrays

Union refers to the set of all the elements of the 2 arrays. Intersection here refers to the set of elements which are common in both the arrays.

Steps to find union of 2 arrays:

1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then print a1[i] and increment i.
3) If a1[i] > a2[j] then print a2[j] and increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.
5) Print remaining elements of the larger array.

int find_union(int arr1[], int arr2[], int SIZE1, int SIZE2)
{
  int i = 0, j = 0;
  while(i < SIZE1 && j < SIZE2)
  {
    if(arr1[i] < arr2[j])
      printf(" %d ", arr1[i++]);
    else if(arr2[j] < arr1[i])
      printf(" %d ", arr2[j++]);
    else
    {
      printf(" %d ", arr1[i]);
      i++; j++;
    }
  }

  /* Print remaining elements of the larger array */
  while(i < SIZE1)
   printf(" %d ", arr1[i++]);
  while(j < SIZE2)
   printf(" %d ", arr2[j++]);
}

Complexity: O(N) N is size of larger array

Steps to find intersection of 2 arrays:

1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then increment i.
3) If a1[i] > a2[j] then increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.

int find_intersection(int arr1[], int arr2[], int SIZE1, int SIZE2)
{
	int i = 0, j = 0;
	while(i < SIZE1 && j < SIZE2)
	{
		if(arr1[i] < arr2[j])
			i++;
		else if(arr2[j] < arr1[i])
			j++;
		else
		{
			printf(" %d ", arr1[i]);
			i++; j++;
		}
	}

}

Complexity: O(N), N is size of larger array

3 Thoughts on “Find Union and Intersection of 2 sorted arrays

  1. gaurav on July 16, 2013 at 4:44 am said:

    these methods will work only when arrays are sorted na??

  2. crazyadmin on July 16, 2013 at 9:26 am said:

    Yes, Otherwise you will have to sort the arrays.. Use Quick Sort for O(N logN)

  3. Dinesh on May 2, 2016 at 4:07 pm said:

    Above union code will fail if the input will be like below

    Array1 = (1, 3, 4, 5, 7, 8)
    Array2 = (2, 3, 5, 16)

    Am i right?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation