Common in 3 Sorted Arrays

Time: O(n1+n2+n3)

Space: O(1)

Intuition

Because all three arrays are sorted, we can move three pointers in one pass instead of checking every pair/triple. At each step, if values are not equal, only pointers at smaller values need to move (they can never catch up unless advanced). This gives linear-time intersection across all three arrays.

Algorithm

1Initialize i, j, k = 0 for arrays a, b, c.
2While all pointers are in range, compare a[i], b[j], c[k].
3If all equal, append value to answer only if it is different from the last added value (dedupe), then increment all three pointers.
4Otherwise compute mx = max(a[i], b[j], c[k]).
5Advance i while a[i] < mx, advance j while b[j] < mx, advance k while c[k] < mx.
6Continue until one pointer reaches the end.

Example Walkthrough

Input: a=[1,5,5], b=[3,4,5,5,10], c=[5,5,10,20]

1.Start: (1,3,5), mx=5. Move i to first 5 and j to first 5.
2.Now (5,5,5) equal -> add 5, move all pointers.
3.Again (5,5,5) equal but duplicate output; skip adding due to dedupe check.
4.Pointers progress until one array ends. Final answer contains only unique commons.

Output: [5]

Common Pitfalls

•Do not add duplicates repeatedly; check last inserted value before appending.
•Move only pointers with values below current maximum when values differ.
•This method requires sorted input arrays; it is invalid for unsorted arrays.

Common in 3 Sorted Arrays.java

Java


import java.util.*;

class Solution {
    // Approach: Three pointers on sorted arrays; align them to the current maximum
    // and record equal matches once (deduplicate in result).
    // Time: O(n1+n2+n3) Space: O(1) extra (excluding output)

    public ArrayList<Integer> commonElements(int[] a, int[] b, int[] c) {
        ArrayList<Integer> ans = new ArrayList<>();

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

        while (i < a.length && j < b.length && k < c.length) {
            if (a[i] == b[j] && b[j] == c[k]) {
                if ((!ans.isEmpty() && ans.get(ans.size() - 1) != a[i]) || ans.isEmpty()) {
                    ans.add(a[i]);
                }
                i++;
                j++;
                k++;

            }
            if (i >= a.length || j >= b.length || k >= c.length) {
                break;
            }
            int max = Math.max(a[i], Math.max(b[j], c[k]));

            while (i < a.length && a[i] < max) {
                i++;
            }
            while (j < b.length && b[j] < max) {
                j++;
            }
            while (k < c.length && c[k] < max) {
                k++;
            }

        }

        return ans;
    }
}

Was this solution helpful?