- Given two sorted integer arrays containing unique or distinct elements.
- We would like to find out the union of two sorted arrays.
- The union of two arrays X & Y will contain elements:
- Common elements of array X & Y.
- Rest of elements of array X
- Rest of elements of array Y.
1. Examples of union of two sorted integer arrays in java
Example #1:
- Given X= { 1, 2, 3, 4 } & Y = {3, 4, 7, 9}
- We would like to find out the union of two sorted arrays.
- Union of X U Y is {1, 2, 3, 4, 7, 9}
Example #2:
- Given X = { 10, 12, 16, 20 } & Y = {12, 18, 20, 22}
- We would like to find out the union of two sorted arrays.
- Union of X U Y is {10, 12, 16, 18, 20, 22}
2. Algorithm – find union of two sorted integer arrays in java
- Given two sorted arrays containing unique elements.
- Start traversing the both arrays, till we reach end of any array
- if element of first array is less than second array
- Print current element of first array
- Increment index of first array
- if element of second array is less than first array
- Print current element second array
- increment index of second array
- else, elements of both arrays are equal
- print current element of any array (it is common element)
- increment index of both arrays
- if element of first array is less than second array
- end of loop.
- Print all elements of first array (if remaining)
- Print all elements of second array (if remaining)
- We will get union of two sorted arrays
Time complexity of algorithm is O (m +n)
3. Program – find union of two sorted integer arrays in java (example)
package org.learn.arrays; import java.util.Arrays; public class UnionSortedArrays { public static void main(String[] args) { int[] firstArray = { 1, 2, 3, 4 }; int[] secondArray = { 3, 4, 7, 9 }; String arr1 = Arrays.toString(firstArray); String arr2 = Arrays.toString(secondArray); System.out.printf("1. First array is : %s", arr1); System.out.printf("\n2. Second array is : %s", arr2); System.out.printf("\n3. Union of two sorted arrays is : "); union(firstArray, secondArray); firstArray = new int[] { 10, 12, 16, 20 }; secondArray = new int[] { 12, 18, 20, 22 }; arr1 = Arrays.toString(firstArray); arr2 = Arrays.toString(secondArray); System.out.println("\n"); System.out.printf("1. First array is : %s", arr1); System.out.printf("\n2. Second array is : %s", arr2); System.out.printf("\n3. Union of two sorted arrays is :"); union(firstArray, secondArray); } private static void union(int[] arr1, int[] arr2) { int length1 = arr1.length; int length2 = arr2.length; int index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { if (arr1[index1] < arr2[index2]) { System.out.printf(" %d", arr1[index1]); index1++; } else if (arr1[index1] > arr2[index2]) { System.out.printf(" %d", arr2[index2]); index2++; } else { System.out.printf(" %d", arr1[index1]); index1++; index2++; } } while (index1 < length1) { System.out.printf(" %d", arr1[index1++]); } while (index2 < length2) { System.out.printf(" %d", arr2[index2++]); } } }
4. Output – find union of two sorted integer arrays in java (example)
1. First array is : [1, 2, 3, 4] 2. Second array is : [3, 4, 7, 9] 3. Union of two sorted arrays is : 1 2 3 4 7 9 1. First array is : [10, 12, 16, 20] 2. Second array is : [12, 18, 20, 22] 3. Union of two sorted arrays is : 10 12 16 18 20 22