19. Find Common Elements in 3 Sorted Arrays

Given three sorted arrays, print the distinct elements common to all three, in ascending order, space-separated. If there are none, print 'None'.

Input: The input contains three sorted arrays, each given as a line with the array's size followed by a line of that many space-separated integers. Output: Print the distinct elements common to all three arrays, in ascending order, space-separated; print 'None' if there are none.

1 <= n1, n2, n3 <= 10^5

This is a direct three-way extension of the two-pointer 'merge' technique - recognizing that connection makes the three-pointer logic feel like a natural generalization rather than a brand new idea.

Given three separately sorted arrays, find every distinct value that appears in ALL three. Brute force: For every element of the first array, scan the other two arrays directly checking for its presence - this costs O(n1 * (n2 + n3)), slower than necessary given that all three arrays are already sorted. Optimised: A three-pointer merge-style walk (extending the classic two-pointer merge idea to three arrays) advances only the pointer(s) pointing at the smallest current value, guaranteeing every element is visited at most once across all three arrays - turning an O(n1*(n2+n3)) search into a single linear O(n1+n2+n3) pass.

For every element of the first array, scan the entire second array and the entire third array looking for a matching value, and collect it as a common element if found in both (skipping duplicates already recorded). This checks every combination directly and is correct regardless of whether the arrays are sorted, but it completely ignores the fact that all three inputs are sorted. Time: O(n1 * n2 * n3) Space: O(1) extra (excluding output)

Exploit that all three arrays are sorted using three pointers, one per array, all starting at index 0. Compare the three current elements: if all three are equal, record the value (advance all three, skipping further duplicates); otherwise advance the pointer(s) pointing at the smallest current value, since a smaller value can never match a larger one later. This mirrors the merge step of merge-sort across three lists, achieving the same linear time as the hashing approach but with only O(1) extra space, since no auxiliary hash sets are needed at all. Time: O(n1 + n2 + n3) Space: O(1) extra (excluding output)

Insert every value of the second and third arrays into two hash sets. Then scan the first array once (skipping consecutive duplicates since it's sorted), and for each distinct value check membership in both hash sets, recording it if present in both. This replaces the two inner linear scans of brute force with O(1) average hash lookups, at the cost of extra memory to store the hash sets. Time: O(n1 + n2 + n3) average Space: O(n2 + n3)

1. Keep one pointer into each of the three arrays, all starting at the beginning. 2. Compare the three pointers' current values - if all three match, that's a common element (print it and advance all three pointers). 3. Otherwise, advance whichever pointer(s) point to the SMALLEST current value(s), since sorted order guarantees they can never match the larger ones without moving forward first. 4. Continue until any one array is exhausted.

Time: O(n1 + n2 + n3) - each pointer only ever moves forward, so the total combined movement is linear in the arrays' combined size. Space: O(1) extra space beyond the output list of common elements.

n1 = n2 = n3 = 1 (smallest possible arrays); no element common to all three (print 'None'); and arrays at the largest size 10^5 (confirming the three-pointer walk is O(n1+n2+n3)).

Be ready to generalize this three-pointer technique to 'k sorted arrays' if asked - the same idea (always advance whichever pointer holds the smallest value) extends naturally, though a min-heap becomes more practical once k grows large.