Code Implementation

class Solution:
    def arraysIntersection(self, arr1, arr2, arr3):
        i, j, k = 0, 0, 0
        res = []
        while i < len(arr1) and j < len(arr2) and k < len(arr3):
            if arr1[i] == arr2[j] == arr3[k]:
                res.append(arr1[i])
                i += 1
                j += 1
                k += 1
            else:
                min_val = min(arr1[i], arr2[j], arr3[k])
                if arr1[i] == min_val:
                    i += 1
                if arr2[j] == min_val:
                    j += 1
                if arr3[k] == min_val:
                    k += 1
        return res
      

class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        int i = 0, j = 0, k = 0;
        vector<int> res;
        while (i < arr1.size() && j < arr2.size() && k < arr3.size()) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                res.push_back(arr1[i]);
                i++; j++; k++;
            } else {
                int min_val = min(arr1[i], min(arr2[j], arr3[k]));
                if (arr1[i] == min_val) i++;
                if (arr2[j] == min_val) j++;
                if (arr3[k] == min_val) k++;
            }
        }
        return res;
    }
};
      

class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        int i = 0, j = 0, k = 0;
        List<Integer> res = new ArrayList<>();
        while (i < arr1.length && j < arr2.length && k < arr3.length) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                res.add(arr1[i]);
                i++; j++; k++;
            } else {
                int minVal = Math.min(arr1[i], Math.min(arr2[j], arr3[k]));
                if (arr1[i] == minVal) i++;
                if (arr2[j] == minVal) j++;
                if (arr3[k] == minVal) k++;
            }
        }
        return res;
    }
}
      

var arraysIntersection = function(arr1, arr2, arr3) {
    let i = 0, j = 0, k = 0;
    const res = [];
    while (i < arr1.length && j < arr2.length && k < arr3.length) {
        if (arr1[i] === arr2[j] && arr2[j] === arr3[k]) {
            res.push(arr1[i]);
            i++; j++; k++;
        } else {
            let minVal = Math.min(arr1[i], arr2[j], arr3[k]);
            if (arr1[i] === minVal) i++;
            if (arr2[j] === minVal) j++;
            if (arr3[k] === minVal) k++;
        }
    }
    return res;
};
      

Problem Description

Given three strictly increasing integer arrays arr1, arr2, and arr3, your task is to return a sorted array containing only the integers that appear in all three arrays.

• Each element in the output must appear in all three input arrays.
• You must not reuse elements; that is, each match should be based on the same value and position in the arrays.
• The arrays are already sorted in strictly increasing order, which means no duplicates within a single array and each next value is larger than the previous.
• Return the result as a sorted array.

Thought Process

The first idea that comes to mind is to check every element of one array against the other two. For example, for each element in arr1, we could check if it exists in arr2 and arr3. However, this brute-force approach would be inefficient, especially for large arrays, since searching through arrays repeatedly can take a lot of time.

But since all arrays are sorted and strictly increasing, we can take advantage of this property. We can use a method similar to merging in merge sort, using three pointers to walk through the arrays in sync. This way, we only need to scan through each array once, comparing the current elements and advancing the pointers smartly.

Solution Approach

• Step 1: Initialize three pointers, one for each array (i for arr1, j for arr2, k for arr3), all starting at 0.
• Step 2: While none of the pointers has reached the end of their respective arrays, compare the elements at these pointers.
• Step 3: If all three elements are equal, add the value to the result array and advance all three pointers by 1.
• Step 4: If the elements are not equal, advance the pointer(s) that point to the smallest value(s). This is because, due to the arrays being strictly increasing, only the larger values might match later, and the smaller ones can be skipped.
• Step 5: Repeat the process until at least one pointer reaches the end of its array.
• Step 6: Return the result array, which will be sorted because all input arrays are sorted.

This approach ensures that we only look at each element once, making the solution efficient and elegant.

Example Walkthrough

Let's walk through an example:

Input:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 5, 7, 9]
arr3 = [1, 3, 4, 5, 8]

• Start with i = 0, j = 0, k = 0: All three arrays have 1 at these positions. Add 1 to result, increment all pointers.
• Now arr1[1]=2, arr2[1]=2, arr3[1]=3: 2, 2, 3. The smallest is 2. Increment i and j (since both have 2).
• Now arr1[2]=3, arr2[2]=5, arr3[1]=3: 3, 5, 3. The smallest is 3. Increment i and k (both have 3).
• Now arr1[3]=4, arr2[2]=5, arr3[2]=4: 4, 5, 4. The smallest is 4. Increment i and k (both have 4).
• Now arr1[4]=5, arr2[2]=5, arr3[3]=5: 5, 5, 5. All equal! Add 5 to result, increment all pointers.
• At this point, one or more pointers reach the end. We're done.

Output: [1, 5]

Time and Space Complexity

• Brute-force approach: For each element in arr1, check if it exists in arr2 and arr3. This would take O(N1 * (N2 + N3)) time, where N1, N2, N3 are the lengths of the arrays.
• Optimized approach (three pointers): Each pointer only moves forward and never backtracks. So, the total number of steps is O(N1 + N2 + N3), since each element is visited at most once.
• Space Complexity: O(1) extra space (not counting the output array), since we just use a few pointers and the result array.

Summary

By leveraging the fact that the input arrays are strictly increasing and sorted, we can use three pointers to efficiently find the intersection. This method avoids unnecessary repeated scanning and ensures an optimal O(N1 + N2 + N3) time complexity. The approach is simple, intuitive, and highlights the power of utilizing input constraints to design efficient algorithms.