Union and Intersection of two sorted arrays (Java)
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.
- If arr1[p1] is smaller than arr2[p2], then add arr1[p1] to res, and increment p1.
- If arr1[p1 is larger than arr2[p2], then add arr2[p2] to res, and increment p2.
- If they are the same, then add one of them to res, and increment both p1 and p2.
- 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.
- If arr1[p1] is smaller than arr2[p2], increment p1.
- If arr1[p1 is larger than arr2[p2], then increment p2.
- If they are the same, then add one of them to res, and increment both p1 and p2.
Java Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
import java.util.ArrayList; import java.util.List; public class UnionIntersection { public List<Integer> union(int[] list1, int[] list2) { List<Integer> res = new ArrayList<>(); int p1 = 0; int p2 = 0; while(p1 < list1.length && p2 < list2.length) { if (list1[p1] < list2[p2]) { res.add(list1[p1]); p1++; } else if(list1[p1] > list2[p2]) { res.add(list2[p2]); p2++; }else { res.add(list1[p1]); p1++; p2++; } } while(p1 < list1.length) { res.add(list1[p1]); p1++; } while(p2 < list2.length) { res.add(list2[p2]); p2++; } return res; } public List<Integer> intersect(int[] list1, int[] list2) { List<Integer> res = new ArrayList<>(); int p1 = 0; int p2 = 0; while(p1 < list1.length && p2 < list2.length) { if (list1[p1] < list2[p2]) { p1++; } else if(list1[p1] > list2[p2]) { p2++; }else { res.add(list1[p1]); p1++; p2++; } } return res; } public static void main(String[] args) { int[] a1 = {1, 2, 3, 4, 5, 6}; int[] a2 = {4, 5, 6, 7, 9, 10}; List<Integer> union = new UnionIntersection().union(a1, a2); System.out.println(union); List<Integer> intersect = new UnionIntersection().intersect(a1, a2); System.out.println(intersect); } } |
Output:
[1, 2, 3, 4, 5, 6, 7, 9, 10]
[4, 5, 6]
Reference:
Finding intersection of two sorted arrays
