Common Element in Sorted Array

We are provided with three arrays sorted in non-decreasing order. The objective is to identify and print all elements that are common among these arrays.

Example 1

Input: 

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

Example 2

Input: 

arr1[] = {1, 5, 5} 

arr2[] = {3, 4, 5, 5, 10} 

arr3[] = {5, 5, 10, 20} 

Output: 5, 5

Approach

1. Initialize three-pointers, one for each array, to point to the first element of each array.
   Let's call these pointers i, j, and k for the three arrays, respectively.
2. Enter a loop that continues as long as all three pointers are within the bounds of their respective arrays.
3. Compare the elements at the current positions pointed to by i, j, and k.
4. If the elements at all three positions are equal, it means you've found a common element. Add it to a list of common elements.
5. If the elements are not equal, move the pointer pointing to the smallest element to the right to potentially find a common element in the next iteration.
6. Repeat steps 3 to 5 until any one of the pointers reaches the end of its respective array.
7. After exiting the loop, the list of common elements contains all the elements that are common to all three sorted arrays.
8. Return the list of common elements as the result.

Complexity

• Time Complexity: O(n), where 'n' is the total number of elements in the three input arrays.
• Space Complexity: O(m), where 'm' is the number of common elements in the three arrays.

Code

#Java Code

import java.util.ArrayList;
import java.util.List;

public class CommonElementsFinder {

    public List<Integer> findCommonElements(int[] firstArray, int[] secondArray, int[] thirdArray) {
        List<Integer> commonElements = new ArrayList<>();
        int pointer1 = 0, pointer2 = 0, pointer3 = 0;

        while (pointer1 < firstArray.length && pointer2 < secondArray.length && pointer3 < thirdArray.length) {
            if (firstArray[pointer1] == secondArray[pointer2] && secondArray[pointer2] == thirdArray[pointer3]) {
                commonElements.add(firstArray[pointer1]);
                pointer1++;
                pointer2++;
                pointer3++;
            } else if (firstArray[pointer1] < secondArray[pointer2]) {
                pointer1++;
            } else if (secondArray[pointer2] < thirdArray[pointer3]) {
                pointer2++;
            } else {
                pointer3++;
            }
        }

        return commonElements;
    }

    public static void main(String[] args) {
        CommonElementsFinder finder = new CommonElementsFinder();
        int[] firstArray = {1, 5, 10, 20, 40, 80};
        int[] secondArray = {6, 7, 20, 80, 100};
        int[] thirdArray = {3, 4, 15, 20, 30, 70, 80, 120};

        List<Integer> commonElements = finder.findCommonElements(firstArray, secondArray, thirdArray);

        System.out.println("Common elements in the three arrays: " + commonElements);
    }
}

Output

Common elements in the three arrays: [20, 80]

Summary

The approach employs three pointers to navigate three sorted arrays. It iteratively compares elements at the current pointers, incrementing the pointer pointing to the smallest element. This systematic comparison efficiently identifies common elements. The sorted nature of the arrays allows for a streamlined process, resulting in a time complexity linearly proportional to the sum of array lengths.