Java - Find Common Elements in Three Sorted Arrays

Problem Statement

Given three sorted arrays, find the elements that are common in all three 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, 2, 3, 4};

arr2 = {2, 3, 4, 5};

arr3 = {3, 4, 5, 6};

Output: [3, 4]

Approach: Using Three Pointers (O(N))

Since all three arrays are sorted, we can use a three-pointer approach to find common elements efficiently.

Algorithm:

Initialize three pointers i, j, k at 0 for the three arrays.

Compare the elements:

If arr1[i] == arr2[j] == arr3[k], add it to the result and move all three pointers forward.

If arr1[i] is smaller, move i forward.

If arr2[j] is smaller, move j forward.

If arr3[k] is smaller, move k forward.

Repeat until any array is fully traversed.

Return the list of common elements.

Implementation

import java.util.ArrayList;

import java.util.List;

public class CommonElements {

public static List<Integer> findCommon(int[] arr1, int[] arr2, int[] arr3) {

List<Integer> result = new ArrayList<>();

int i = 0, j = 0, k = 0;

while (i < arr1.length && j < arr2.length && k < arr3.length) {

if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {

// Add to result if not already present

if (result.isEmpty() || result.get(result.size() - 1) != arr1[i]) {

result.add(arr1[i]);

}

i++; j++; k++;

}

else if (arr1[i] < arr2[j]) {

i++;

}

else if (arr2[j] < arr3[k]) {

j++;

}

else {

k++;

}

return result;

}

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};

List<Integer> common = findCommon(arr1, arr2, arr3);

System.out.println(common); // Output: [20, 80]

}

Complexity Analysis

Approach Time Complexity Space Complexity

Three Pointers O(N + M + P) O(1) (excluding output list)

Why O(N + M + P)?

Each element in the three arrays is processed at most once.

The worst case occurs when all elements are different.

Alternative Approach: Using HashMap (O(N) Space)

Store counts of elements in arr1 in a HashMap.

Check occurrences in arr2 and arr3.

Collect only those present in all three.

Code:

import java.util.*;

public class CommonElementsUsingMap {

public static List<Integer> findCommon(int[] arr1, int[] arr2, int[] arr3) {

Map<Integer, Integer> countMap = new HashMap<>();

for (int num : arr1) countMap.put(num, 1);

for (int num : arr2) if (countMap.containsKey(num)) countMap.put(num, 2);