Find intersection/common elements of two sorted integer arrays in java (example)

  • Given two sorted arrays containing distinct elements.
  • We would like to find out the intersection of two sorted arrays.
    • Intersection is nothing but the common elements of two sorted arrays.

1. Examples: intersection or common elements of two sorted arrays in java

Example #1:

  • Given X= { 1, 2, 3, 4 } &  Y = {3, 4, 7, 9}
  • We would like to find out the intersection of two arrays.
  • The intersection X ∩ Y or common elements of two arrays is {3,4}

Example #2:

  • Given X= { 10, 12, 16, 20 } &  Y = {12, 18, 20, 22}
  • We would like to find out the intersection of two arrays.
  • The intersection X ∩ Y or common elements of two arrays is {12,20}

2. Algorithm – Intersections of two sorted integer arrays in java (example)

  • 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
      • increment index of first array
    • if element of second array is less than first array
      • increment index of second array
    • else, elements of both arrays are equal
      • print element (it is common element)
      • increment index of both arrays
  • end of traversal of loop.
  • We will get intersection of two sorted arrays

Time complexity of algorithm is O (m+n)

3. Program – Intersection or common element of two sorted arrays in java

package org.learn.arrays;
 
import java.util.Arrays;
 
public class IntersectionSortedArrays {
 
    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. Intersection of two sorted arrays is :");
        intersection(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. Intersection of two sorted arrays is :");
        intersection(firstArray, secondArray);
    }
 
    private static void intersection(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]) {
                index1++;
            } else if (arr1[index1] > arr2[index2]) {
                index2++;
            } else {
                System.out.printf(" %d", arr1[index1]);
                index1++;
                index2++;
            }
        }
    }
}

4. Output – Intersection 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. Intersection of two sorted arrays is : 3 4
 
1. First array is : [10, 12, 16, 20]
2. Second array is : [12, 18, 20, 22]
3. Intersection of two sorted arrays is : 12 20