Intersection of Two Sorted Arrays

Problem

Given two sorted arrays, return their intersection, including duplicate matches where they occur in both.

Input:  arr1 = [1, 2, 2, 3], arr2 = [2, 2, 4]
Output: [2, 2]

Python Solution

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

C++ Solution

vector<int> intersectionSorted(vector<int>& arr1, vector<int>& arr2) {
    int i = 0, j = 0;
    vector<int> result;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) i++;
        else if (arr2[j] < arr1[i]) j++;
        else {
            result.push_back(arr1[i]);
            i++; j++;
        }
    }
    return result;
}

Java Solution

class Solution {
    public List<Integer> intersectionSorted(int[] arr1, int[] arr2) {
        int i = 0, j = 0;
        List<Integer> result = new ArrayList<>();
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) i++;
            else if (arr2[j] < arr1[i]) j++;
            else {
                result.add(arr1[i]);
                i++; j++;
            }
        }
        return result;
    }
}

Complexity

Time: O(m + n) — each pointer moves forward at least once per step, so together they cross both arrays once. Space: O(min(m, n)) for the output in the worst case, when one array is fully contained in the other.