Problem Description

You are given three integer arrays arr1, arr2, and arr3. Each array is sorted in strictly increasing order (meaning each element is larger than the previous one with no duplicates within a single array).

Your task is to find all integers that appear in all three arrays and return them as a sorted array. In other words, you need to find the intersection of all three arrays - only include numbers that exist in arr1 AND arr2 AND arr3.

For example:

• If arr1 = [1, 2, 3, 4, 5], arr2 = [1, 2, 5, 7, 9], and arr3 = [1, 3, 4, 5, 8]
• The number 1 appears in all three arrays
• The number 5 appears in all three arrays
• The numbers 2, 3, 4, 7, 8, 9 do not appear in all three arrays
• So the result would be [1, 5]

The solution uses a counting approach: it combines all three arrays, counts how many times each number appears across all arrays, and then identifies numbers that appear exactly 3 times (once in each array, since arrays have no duplicates internally). These numbers that appear 3 times are collected and returned as the final result.

Intuition

Since we need to find numbers that appear in all three arrays, we can think about what makes a number qualify for our result. A key observation is that each array is sorted in strictly increasing order, which means there are no duplicate values within a single array.

This property gives us an important insight: if a number appears in all three arrays, it will appear exactly 3 times when we combine all the arrays together - once from each array. Conversely, if a number appears fewer than 3 times in the combined arrays, it means it's missing from at least one array and shouldn't be in our result.

This leads us to a simple counting strategy:

1. Combine all three arrays into one collection
2. Count how many times each unique number appears
3. Any number that appears exactly 3 times must be present in all three arrays

For example, if we have arr1 = [1, 2, 3], arr2 = [2, 3, 4], and arr3 = [3, 4, 5]:

• After combining: [1, 2, 3, 2, 3, 4, 3, 4, 5]
• Counting occurrences: 1 appears 1 time, 2 appears 2 times, 3 appears 3 times, 4 appears 2 times, 5 appears 1 time
• Only 3 appears exactly 3 times, so it's the only number in all three arrays

This approach works because the strictly increasing property guarantees that each number can appear at most once per array, making the count of 3 a reliable indicator that the number exists in all three arrays.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses a counting approach with Python's Counter class to efficiently track occurrences of each number across all three arrays.

Step-by-step implementation:

1. Combine all arrays: First, we concatenate all three arrays into a single list using arr1 + arr2 + arr3. This gives us one collection containing all elements from all three arrays.

2. Count occurrences: We use Counter() from Python's collections module to count how many times each unique number appears in the combined list. The Counter creates a dictionary-like object where keys are the unique numbers and values are their counts.

   cnt = Counter(arr1 + arr2 + arr3)

3. Filter for intersection: We iterate through arr1 (we could use any of the three arrays since all common elements will be present in each) and check if each element has a count of exactly 3 in our counter. If it does, we include it in the result.

   return [x for x in arr1 if cnt[x] == 3]

Why this works:

• Since each array has strictly increasing elements (no duplicates within an array), a number can appear at most once in each array
• If a number appears in all three arrays, it will be counted exactly 3 times
• If a number appears in only one or two arrays, its count will be less than 3
• The result is automatically sorted because we iterate through arr1, which is already sorted

Time Complexity: O(n1 + n2 + n3) where n1, n2, and n3 are the lengths of the three arrays, as we need to traverse all elements once for counting and then traverse one array for filtering.

Space Complexity: O(n1 + n2 + n3) for storing the counter dictionary and the combined array.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• arr1 = [1, 2, 5]
• arr2 = [2, 5, 7]
• arr3 = [1, 5, 7]

Step 1: Combine all arrays We concatenate all three arrays into a single list:

combined = [1, 2, 5, 2, 5, 7, 1, 5, 7]

Step 2: Count occurrences of each number Using a Counter, we count how many times each unique number appears:

Counter results:
- 1 appears 2 times (once from arr1, once from arr3)
- 2 appears 2 times (once from arr1, once from arr2)
- 5 appears 3 times (once from arr1, once from arr2, once from arr3)
- 7 appears 2 times (once from arr2, once from arr3)

Step 3: Filter for numbers that appear exactly 3 times We iterate through arr1 = [1, 2, 5] and check each element:

• 1: count is 2 (not 3) → exclude
• 2: count is 2 (not 3) → exclude
• 5: count is 3 (exactly 3) → include

Result: [5]

The number 5 is the only value that appears in all three arrays. Notice how the counting approach correctly identifies it by finding the element that appears exactly 3 times in the combined list. Since we iterate through arr1 which is already sorted, our result is automatically sorted as well.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n represents the total length of all three arrays combined (i.e., len(arr1) + len(arr2) + len(arr3)). This is because:

• Concatenating the three arrays takes O(n) time
• Creating the Counter from the concatenated list requires iterating through all n elements once, which is O(n)
• The list comprehension iterates through arr1 and performs O(1) lookups in the Counter, resulting in O(len(arr1)) which is bounded by O(n)

The space complexity is O(m), where m represents the number of unique elements across all three arrays. This is because:

• The Counter dictionary stores at most m unique keys (the distinct values appearing in the three arrays)
• The concatenated list arr1 + arr2 + arr3 creates temporary space of O(n), but since we typically have m ≤ n and often m << n for sorted arrays with duplicates, the dominant factor for auxiliary space is the Counter with O(m) space
• The output list in the worst case contains all elements from arr1, but this is bounded by O(m) unique values

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming the counting approach works with arrays containing duplicates

The Issue: The counting approach relies on the fact that each array has strictly increasing elements (no duplicates within a single array). If the arrays could contain duplicates, this approach would fail.

Example of failure with duplicates:

• arr1 = [1, 1, 2], arr2 = [1, 3], arr3 = [2, 3]
• Combined: [1, 1, 2, 1, 3, 2, 3]
• Counter: {1: 3, 2: 2, 3: 2}
• The algorithm would incorrectly return [1] when the actual intersection is empty

Solution: If arrays could contain duplicates, use a set-based approach instead:

def arraysIntersection(self, arr1, arr2, arr3):
    return sorted(set(arr1) & set(arr2) & set(arr3))

Pitfall 2: Memory inefficiency with very large arrays

The Issue: The current approach creates a concatenated list (arr1 + arr2 + arr3) which allocates new memory for all elements, potentially causing memory issues with very large arrays.

Solution: Use a more memory-efficient approach by iterating through arrays individually:

def arraysIntersection(self, arr1, arr2, arr3):
    frequency_counter = Counter()
    for arr in [arr1, arr2, arr3]:
        for num in arr:
            frequency_counter[num] += 1
    return [element for element in arr1 if frequency_counter[element] == 3]

Pitfall 3: Not leveraging the sorted nature for optimization

The Issue: The counting approach has O(n1 + n2 + n3) time complexity but doesn't take advantage of the fact that all arrays are sorted, which could enable a more efficient three-pointer approach.

Solution: Use a three-pointer approach for O(min(n1, n2, n3)) complexity in best case:

def arraysIntersection(self, arr1, arr2, arr3):
    result = []
    i = j = k = 0
  
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        if arr1[i] == arr2[j] == arr3[k]:
            result.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 result

This approach can terminate early when any array is exhausted and doesn't require extra space for counting.