Union and Intersection of two sorted arrays (Java)

Tags: ,

Given two sorted arrays or lists, get their union and intersection.

For example, if the input arrays are:
int[] list1 = {1, 3, 4, 5, 6, 7}
int[] list2 = {2, 3, 5, 6}
Then the union is {1, 2, 3, 4, 5, 6, 7} and the Intersection is {3, 5, 6}.

Analysis

We can solve this problem using the same idea of merging sorted list.

Union of two sorted lists algorithm

 define two index variables p1 and p2, initialized as 0

define List<Integer> res to record the final result.

  1. If arr1[p1] is smaller than arr2[p2], then add arr1[p1]  to res, and increment p1.
  2. If arr1[p1 is larger than arr2[p2], then add arr2[p2]  to res, and increment p2.
  3. If they are the same, then add one of them to res, and increment both p1 and p2. 
  4. add the remaining elements in the larger ary to res.

Intersection of two sorted Lists algorithm

define two index variables p1 and p2, initialized as 0

define List<Integer> res to record the final result.

  1. If arr1[p1] is smaller than arr2[p2],  increment p1.
  2. If arr1[p1 is larger than arr2[p2], then  increment p2.
  3. If they are the same, then add one of them to res, and increment both p1 and p2. 

Java Implementation

Output:

[1, 2, 3, 4, 5, 6, 7, 9, 10]
[4, 5, 6]

Reference:

Finding intersection of two sorted arrays