Intersection of Three Sorted Arrays - Practice Coding Problems

Intersection of Three Sorted Arrays - Problem

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Since all arrays are already sorted, we can take advantage of this property to find common elements efficiently.

Key points:

All arrays are sorted in strictly increasing order (no duplicates within each array)
We need elements that appear in all three arrays
The result should be sorted (naturally will be due to input being sorted)

Input & Output

Example 1 — Basic Case

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

› Output: [1,5]

💡 Note: Elements 1 and 5 appear in all three arrays. Element 1 is at index 0 in all arrays, and element 5 appears in positions: arr1[4], arr2[2], arr3[3].

Example 2 — No Common Elements

$ Input: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]

› Output: []

💡 Note: No element appears in all three arrays, so the result is empty.

Example 3 — Single Common Element

$ Input: arr1 = [1,2,3], arr2 = [2,3,4], arr3 = [2,4,5]

› Output: [2]

💡 Note: Only element 2 appears in all three arrays: arr1[1], arr2[0], arr3[0].

Constraints

1 ≤ arr1.length, arr2.length, arr3.length ≤ 1000
-10⁵ ≤ arr1[i], arr2[i], arr3[i] ≤ 10⁵
All arrays are sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Three sorted arrays with some overlapping elements

Find Intersection

Identify elements that appear in all three arrays

Output Result

Return sorted array of common elements

Key Takeaway

🎯 Key Insight: Use three pointers to traverse sorted arrays simultaneously, advancing the pointer with the smallest current value until all three match.

Asked in

G Google 35 a Amazon 28 F Facebook 22 M Microsoft 18

The key insight is to leverage the sorted property of all three arrays. The optimal three pointers approach traverses all arrays simultaneously, comparing current elements and advancing pointers strategically. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Three Pointers (Optimal)	O(n)	O(1)	Use three pointers to traverse all arrays simultaneously, taking advantage of sorted property
Brute Force - Triple Nested Loop	O(n³)	O(1)	Check each element in arr1 against all elements in arr2 and arr3
Hash Map Frequency Count	O(n)	O(n)	Count occurrences of each element across all three arrays using a hash map

Three Pointers (Optimal) — Algorithm Steps

Initialize three pointers at start of each array
Compare elements at current positions
If all three equal, add to result and advance all pointers
If not equal, advance pointer(s) with smaller value
Continue until any pointer reaches end

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start three pointers at beginning of each array

Compare

Compare current elements at pointer positions

Advance

Move pointer(s) with smaller values forward

Match

When all three match, add to result and advance all

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* arr1, int arr1Size, int* arr2, int arr2Size, int* arr3, int arr3Size, int* returnSize) {
    int* result = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    int i = 0, j = 0, k = 0;
    
    while (i < arr1Size && j < arr2Size && k < arr3Size) {
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            result[(*returnSize)++] = arr1[i];
            i++;
            j++;
            k++;
        } else if (arr1[i] < arr2[j]) {
            i++;
        } else if (arr2[j] < arr3[k]) {
            j++;
        } else {
            k++;
        }
    }
    
    return result;
}

int main() {
    // Simple parsing for demo
    int arr1[] = {1,2,3,4,5};
    int arr2[] = {1,2,5,7,9};
    int arr3[] = {1,3,4,5,8};
    
    int returnSize;
    int* result = solution(arr1, 5, arr2, 5, arr3, 5, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all arrays where n is total number of elements

✓ Linear Growth

Space Complexity

O(1)

Only using three pointer variables and result array (not counted as extra space)

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Three Pointers (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler