Find common elements In 3 sorted arrays

Problem Statement

Given three sorted arrays, find all common elements that appear in all three arrays.

Example:

• 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]

Approach 1: Brute Force

Intuition

For each element in the first array, search for it in the other two arrays.

Algorithm

1. For each element in arr1
2. Check if it exists in arr2 (linear or binary search)
3. If found, check if it exists in arr3
4. If found in all three, add to result

import java.util.*;

public class Solution {
    private boolean binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return true;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
    
    public List<Integer> findCommonBruteForce(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> result = new ArrayList<>();
        
        for (int num : arr1) {
            if (binarySearch(arr2, num) && binarySearch(arr3, num)) {
                // Avoid duplicates in result
                if (result.isEmpty() || result.get(result.size() - 1) != num) {
                    result.add(num);
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n1 × log(n2) × log(n3)) with binary search, O(n1 × n2 × n3) with linear search
• Space Complexity: O(1) - Excluding output space

Approach 2: Three Pointers (Optimal)

Intuition

Since all arrays are sorted, use three pointers, one for each array. Move the pointer pointing to the smallest element. If all three pointers point to equal elements, we found a common element.

Algorithm

1. Initialize three pointers i, j, k at the start of each array
2. While none of the pointers exceed their array bounds:
   • If all three elements are equal, add to result and advance all pointers
   • Otherwise, advance the pointer pointing to the smallest element
3. Return result

import java.util.*;

public class Solution {
    public 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 all three are equal
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                // Avoid duplicates in result
                if (result.isEmpty() || result.get(result.size() - 1) != arr1[i]) {
                    result.add(arr1[i]);
                }
                i++;
                j++;
                k++;
            }
            // Move the pointer pointing to the smallest element
            else if (arr1[i] < arr2[j]) {
                i++;
            }
            else if (arr2[j] < arr3[k]) {
                j++;
            }
            else {
                k++;
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n1 + n2 + n3) - Each element is visited at most once
• Space Complexity: O(1) - Only three pointers used

Visual Example

For arrays:

• arr1 = [1, 5, 10, 20, 40, 80]
• arr2 = [6, 7, 20, 80, 100]
• arr3 = [3, 4, 15, 20, 30, 70, 80, 120]

Generalized Solution for N Arrays

Key Takeaways

1. Three pointer technique is a natural extension of two pointers
2. Since arrays are sorted, we can efficiently skip elements
3. Always move the pointer with the smallest value
4. Handle duplicates by checking before adding to result
5. This technique works because: if smallest value doesn't match, it can never be common
6. Generalizable: Can extend to N sorted arrays using iterative intersection