Intersection of Two Sorted Arrays

Summary

Given two sorted arrays, find their intersection. The intersection is the set of elements that are present in both arrays.

This problem involves arrays and sorting concepts, making it an easy algorithmic problem to solve.

Detailed Explanation

The approach to this problem is straightforward. We iterate through both arrays simultaneously, comparing the current elements at each step. If the elements match, we add them to our result set. Since the arrays are sorted, we know that if the elements don't match, one array's element will always be smaller than the other.

Here's a step-by-step breakdown of the solution:

1. Initialize two pointers, i and j, for each array at index 0.
2. Compare the current elements at indices i and j. If they are equal, add the common element to our result set.
3. Move the pointer that points to the smaller element forward (since we know the arrays are sorted).
4. Repeat steps 2-3 until one array is exhausted.

Time complexity: O(n + m), where n and m are the sizes of the two input arrays, since we process each element once.

Space complexity: O(min(n, m)), since in the worst-case scenario (when all elements are unique), our result set can have up to min(n, m) elements.

Optimized Solutions

Java

java
public int[] intersection(int[] A, int[] B) {
    int i = 0, j = 0;
    List<Integer> result = new ArrayList<>();
    while (i < A.length && j < B.length) {
        if (A[i] == B[j]) {
            result.add(A[i]);
            i++;
            j++;
        } else if (A[i] < B[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

Python

python
def intersection(A, B):
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        if A[i] == B[j]:
            result.append(A[i])
            i += 1
            j += 1
        elif A[i] < B[j]:
            i += 1
        else:
            j += 1
    return [i for i in result]

C++

cpp
vector<int> intersection(vector<int>& A, vector<int>& B) {
    int i = 0, j = 0;
    set<int> result;
    while (i < A.size() && j < B.size()) {
        if (A[i] == B[j]) {
            result.insert(A[i]);
            i++;
            j++;
        } else if (A[i] < B[j]) {
            i++;
        } else {
            j++;
        }
    }
    vector<int> res(result.begin(), result.end());
    return res;
}

JavaScript

javascript
function intersection(A, B) {
    let i = 0, j = 0;
    const result = [];
    while (i < A.length && j < B.length) {
        if (A[i] === B[j]) {
            result.push(A[i]);
            i++;
            j++;
        } else if (A[i] < B[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

Note: The optimized solutions provided are in the form of a function that takes two arrays as input and returns their intersection.