# Intersection of Two Sorted Arrays

Finding the intersection of two sorted arrays is a common problem in coding interviews and programming challenges. In this article, we'll discuss two approaches to solve this problem: one using a brute force approach and another using two-pointers technique.

### Solution 1: Brute Force Approach (using Nested Loop)

This method involves using a nested loop to find the intersection of two arrays.

**Implementation**:

```cpp
// Solution-1: Brute Force Approach
// Time Complexity: O(m * n)
// Space Complexity: O(m)
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    vector<int> temp;
    vector<int> visited(m, 0);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // If element matches and has not been matched with any element before
            if (arr1[i] == arr2[j] && visited[j] == 0)
            {
                temp.push_back(arr2[j]);
                visited[j] = 1;
                break;
            }
            // As the array is sorted, element will not be beyond this
            else if (arr2[j] > arr1[i])
            {
                break;
            }
        }
    }

    return temp;
}
```

**Logic**:

1. **Track Visited Elements**:
    
    * Initialize a `visited` vector of size `m` (length of `arr2`) with all elements set to `0`. This vector is used to track elements in `arr2` that have already been matched.
        
2. **Nested Loop**:
    
    * Iterate through each element of `arr1` using the outer loop. For each element in `arr1`, iterate through each element of `arr2` using the inner loop.
        
3. **Check for Matches**:
    
    * If the current element of `arr1` matches the current element of `arr2` and the `visited` marker for that element in `arr2` is `0` (indicating it has not been matched yet), add the element to the result vector `temp` and mark it as visited by setting the corresponding element in the `visited` vector to `1`.
        
    * If the current element of `arr2` is greater than the current element of `arr1`, break out of the inner loop as the arrays are sorted and no further match will be found for the current element of `arr1`.
        

**Time Complexity**: O(m \* n)

* **Explanation**: Each element in `arr1` is compared with every element in `arr2`, resulting in a nested loop.
    

**Space Complexity**: O(m)

* **Explanation**: Additional space is used to store the `visited` vector and the result vector `temp`.
    

**Example**:

* **Input**: `arr1 = [1, 2, 2, 3, 4]`, `arr2 = [2, 2, 3, 5, 6]`
    
* **Output**: `intersection = [2, 2, 3]`
    
* **Explanation**: Elements `2` and `3` are common in both arrays.
    

---

### Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to find the intersection efficiently.

**Implementation**:

```cpp
// Solution-2: Optimal Approach (Using Two Pointers)
// Time Complexity: O(m + n)
// Space Complexity: O(min(n, m))
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    int i = 0;
    int j = 0;
    vector<int> temp;

    while (i < n && j < m)
    {
        if (arr1[i] < arr2[j])
        {
            i++;
        }
        else if (arr1[i] > arr2[j])
        {
            j++;
        }
        else
        {
            temp.push_back(arr1[i]);
            i++;
            j++;
        }
    }

    return temp;
}
```

**Logic**:

1. **Initialize Pointers**:
    
    * Initialize two pointers `i` and `j`, both set to `0`. These pointers will traverse `arr1` and `arr2`, respectively.
        
2. **Traverse Arrays**:
    
    * Use a `while` loop to traverse both arrays as long as both pointers are within the bounds of their respective arrays.
        
3. **Compare Elements**:
    
    * If the current element of `arr1` is less than the current element of `arr2`, increment pointer `i` to move to the next element in `arr1`.
        
    * If the current element of `arr1` is greater than the current element of `arr2`, increment pointer `j` to move to the next element in `arr2`.
        
    * If the current elements of both `arr1` and `arr2` are equal, add the element to the result vector `temp` and increment both pointers `i` and `j` to move to the next elements in both arrays.
        

**Time Complexity**: O(m + n)

* **Explanation**: Each array is traversed once using two pointers.
    

**Space Complexity**: O(min(n, m))

* **Explanation**: The result vector `temp` stores the intersection elements, which can be up to the size of the smaller array.
    

**Example**:

* **Input**: `arr1 = [1, 2, 2, 3, 4]`, `arr2 = [2, 2, 3, 5, 6]`
    
* **Output**: `intersection = [2, 2, 3]`
    
* **Explanation**: Elements `2` and `3` are common in both arrays.
    

---

### Comparison

* **Brute Force Approach**:
    
    * **Pros**: Simple and straightforward.
        
    * **Cons**: Inefficient for large arrays due to O(m \* n) time complexity and additional space usage.
        
* **Optimal Approach**:
    
    * **Pros**: Efficient with O(m + n) time complexity and lower space complexity.
        
    * **Cons**: Slightly more complex to implement but highly efficient for large arrays.
        

### Edge Cases

* **Empty Arrays**: Returns an empty array as there are no elements to intersect.
    
* **No Intersection**: Returns an empty array if there are no common elements.
    
* **Identical Arrays**: Returns the entire array as all elements are common.
    

### Additional Notes

* **Efficiency**: The two-pointers technique is more time-efficient, making it preferable for large arrays.
    
* **Practicality**: Both methods handle intersections efficiently but the choice depends on the size of the arrays and space constraints.
    

### Conclusion

Finding the intersection of two sorted arrays can be efficiently achieved using either a brute force approach or a two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.

---