- 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
- if element of first array is less than second array
- 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 |