Find union of two sorted integer or number arrays in java (example)

  • 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}
union sorted array java example
Fig 1: Union of two sorted array

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
  • 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
Scroll to Top