Write a java program to find common elements in three sorted arrays.
Given three sorted arrays, write a code to print intersection of three sorted arrays.
For example –
arr1 = {1, 5, 10, 20, 40, 80};
arr2 = {6, 7, 20, 80, 100};
arr3 = {3, 4, 15, 20, 30, 70, 80, 120};
Output : {20, 80}
20 and 80 are the common elements in 3 arrays. These two elements are the intersection of 3 sorted arrays.
Find common elements in three sorted arrays
We have discussed the problem statement. Before jumping into the solution, let’s think what all approaches we can use to solve this problem. This problem is the extension of find intersection of two sorted arrays.
We will start with the easiest approach and then we will improve our solution to solve this problem efficiently.
Find common elements in three sorted arrays video tutorial
Method 1: Beginner’s Approach
The simplest approach is to use three for loops to find intersection of three sorted arrays.
The time complexity of this approach is O(n^3).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/* * Method to find intersection of three sorted arrays. */ public static void commonElements(int arr1[], int arr2[], int arr3[]) { for(int i = 0; i < arr1.length; i++) { for(int j = 0; j < arr2.length; j++) { for(int k = 0; k < arr3.length; k++) { if(arr1[i] == arr2[j] && arr2[j] == arr3[k]) { System.out.println(arr1[i]); } } } } } |
Find Common Elements in Three Sorted Arrays – Java Code
In our previous approach, we have solved this problem using three for loops. Let’s improve our solution and solve this problem in a single traversal.
The idea here is to traverse all the arrays simultaneously, and if we found common element just print it.
i) Declare three variables (x, y, z) and Initialized with zero.
ii) Run a while loop until the array lengths ( arr1.length > x, arr2.length > y, arr3.length > z) are greater than the declared variables.
iii) At each step compare the values to find the common element (arr1[x] == arr2[y] && arr2[y] == arr3[z]). If it’s found increment the value of all the three variables.
Else increment y if arr1[x] > arr2[y]. Increment z if arr2[y] > arr3[z], else increment x
The time complexity of this approach is O(N1 + N2 + N3).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/** * Optimized way to print common elements of three sorted arrays */ public class FindCommonElementInThree { public static void commonElements(int arr1[], int arr2[], int arr3[]) { //Declare three variables and intialized to zero int x = 0, y = 0, z = 0; while(x < arr1.length && y < arr2.length && z < arr3.length) { if(arr1[x] == arr2[y] && arr2[y] == arr3[z]) { System.out.println(arr1[x]); x++; y++; z++; } else if (arr1[x] > arr2[y]) { y++; } else if (arr2[y] > arr3[z]) { z++; } else { x++; } } } public static void main(String[] args) { int arr1[] = {1, 5, 10, 20, 40, 80}; int arr2[] = {6, 7, 20, 80, 100}; int arr3[] = {3, 4, 15, 20, 30, 70, 80, 120}; commonElements(arr1, arr2, arr3); } } |
Find sum of digits of a number
In this video tutorial, I have explained both the approaches using java code.
