How to find the intersection of two sorted arrays

Intersection of two sorted arrays

Given two sorted arrays, finding their intersection involves returning the elements that appear in both of them. For example, the intersection of the arrays, $[1,1,3,4,7]$ and $[3,6,7,8,15]$, is $[3,7]$. In this Answer, we'll explore how we can efficiently find the intersection of any two given sorted arrays—$arr1$ and $arr2$.

Solution

Since the arrays are sorted, we can simply iterate through both of them simultaneously using different loop counters. While doing so, we can do an element-wise comparison in both arrays, and if both elements are the same, the elements can be added to the intersection (if it hasn't already been added before). However, if the elements are not the same, the counter of one of the arrays is incremented (depending on which element was greater). The whole process is repeated until one of the arrays has been completely traversed. This process is depicted below with an example:

Example

Explanation

The sortedArrayIntersection() function highlighted in the code above is explained below:

• Lines 6–8: We use counter1 to iterate through arr1. We use counter2 to iterate through arr2. This is done until one of the counters exceeds the length of the array it is traversing, in which case we return intersection.

• Lines 10–12: If arr1[counter1] == arr2[counter2] , check whether this element is a duplicate (by comparing it with the previous element of one of the arrays). If it isn't a duplicate, add it to the intersection and increment counter1 and counter2.

• Lines 18–22: If arr1[counter1] > arr2[counter2] , increment counter2 (the arrays are sorted, so the next value in arr2 will be greater than or equal to the current one). Otherwise, increment counter1.

Time complexity

Since this solution only involves traversing through each of the $N$ members of an array only once, it takes a total of $O(N)$ time in the worst case.