- 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 |