Intersection of Two Sorted Arrays

Elements appearing in both arrays, duplicates allowed. [1,2,2,3,3,4,5,6] ∩ [2,3,3,5,6,6,7] = [2,3,3,5,6].

Brute force: for each element in array 1, scan array 2 for an unused match, marking matches visited to correctly handle duplicates.

Optimal — two pointers: since both arrays are sorted, advance whichever pointer points to the smaller value; on a match, record it and advance both.

def array_intersection_two_pointers(arr1, arr2):
    result = []
    i, j = 0, 0

    while i < len(arr1) and j < len(arr2):
        if arr1[i] == arr2[j]:
            result.append(arr1[i])
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1

    return result