Intersection of Three Sorted Arrays

class Solution {
public:
    vector<int> intersectThreeArrays(vector<int>& arr1, vector<int>& arr2,
                                   vector<int>& arr3) {
        vector<int> result;

        int i1 = 0, i2 = 0, i3 = 0;

        while (i1 < arr1.size() && i2 < arr2.size() && i3 < arr3.size()) {
            if (arr1[i1] == arr2[i2] && arr2[i2] == arr3[i3]) {
                result.push_back(arr1[i1]);
                i1++;
                i2++;
                i3++;
            } else {
                if (arr1[i1] < arr2[i2]) {
                    i1++;
                } else if (arr2[i2] < arr3[i3]) {
                    i2++;
                } else {
                    i3++;
                }
            }
        }

        return result;
    }
};

The provided C++ code defines a solution that finds the intersection of three sorted arrays. The function intersectThreeArrays accepts three vectors: arr1, arr2, and arr3, which represent the sorted arrays, and returns a vector containing their common elements in sorted order.

The function implements a triple pointer approach to efficiently traverse each array simultaneously using three pointers: i1, i2, and i3. They respectively point to the current position in arr1, arr2, and arr3. As the function cycles through the arrays:

• Check if the elements pointed at by all three pointers are equal. If they are, add the element to the result vector and increment all three pointers to move to the next elements.
• If the elements are not equal, increment the pointer that points to the smallest element among the three to potentially match it with the next element in the corresponding array.

The process continues until any one of the arrays is completely traversed, ensuring that every comparison operation involves O(1) work and progresses through each array without redundant checks. The algorithm thus efficiently finds the intersection in linear time, relative to the sum of the lengths of the three arrays.

class Solution {

    public List<Integer> findCommonElements(
        int[] firstArray,
        int[] secondArray,
        int[] thirdArray
    ) {
        List<Integer> resultList = new ArrayList<>();
        int index1 = 0, index2 = 0, index3 = 0;

        while (index1 < firstArray.length && index2 < secondArray.length && index3 < thirdArray.length) {
            if (firstArray[index1] == secondArray[index2] && secondArray[index2] == thirdArray[index3]) {
                resultList.add(firstArray[index1]);
                index1++;
                index2++;
                index3++;
            } else {
                if (firstArray[index1] < secondArray[index2]) {
                    index1++;
                } else if (secondArray[index2] < thirdArray[index3]) {
                    index2++;
                } else {
                    index3++;
                }
            }
        }
        return resultList;
    }
}

Addressing the problem of finding the intersection elements in three sorted arrays, this Java solution implements an efficient approach utilizing the simultaneous traversal of all three arrays. Here's a succinct summary of how this code functions:

• Initialize three pointers, one for each array, to track the current element of the respective arrays.
• Use a while loop to iterate through the arrays as long as none of the pointers exceed their respective array lengths.
• Inside the loop, compare the elements pointed by the three pointers.
  • If all three elements are equal, add the element to the result list and increment all three pointers.
  • If there is a mismatch, increment the pointer pointing to the smallest element among the three to potentially find a match in subsequent positions.
• Continue this process until at least one of the arrays is completely traversed.

This algorithm ensures that the time complexity is controlled and proportional to the sum of the lengths of the three arrays, making it efficient for large datasets. The use of a list to collect intersection elements allows for dynamic handling of common elements without knowing their count beforehand. This method excels in situations where arrays are long and the intersection set is expected to be substantially smaller than the input arrays.

class Solution:
    def findCommonElements(self, list1: List[int], list2: List[int], list3: List[int]) -> List[int]:
        result = []
        index1 = index2 = index3 = 0
        while index1 < len(list1) and index2 < len(list2) and index3 < len(list3):
            if list1[index1] == list2[index2] == list3[index3]:
                result.append(list1[index1])
                index1 += 1
                index2 += 1
                index3 += 1
            else:
                if list1[index1] < list2[index2]:
                    index1 += 1
                elif list2[index2] < list3[index3]:
                    index2 += 1
                else:
                    index3 += 1
        return result

This Python solution implements a way to find the intersection of three sorted arrays.

• Initialize an empty list, result, to store the common elements.
• Use three indices (index1, index2, index3) to traverse the arrays (list1, list2, list3), starting all at position 0.
• Use a while loop to continue processing as long as none of the indices exceeds the length of their respective arrays.
• If the elements at list1[index1], list2[index2], and list3[index3] are equal, append this element to the result list and increment all three indices.
• If the elements are not equal, increment the index associated with the smallest element to move closer to finding the next potential common element.
• Return the result list, which contains all common elements among the three arrays.

This approach ensures that the solution efficiently finds all matching numbers in the arrays by only making a single pass through each.