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**:

```
// 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**:

**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.

- Initialize a
**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.

- Iterate through each element of
**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**:

```
// 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**:

**Initialize Pointers**:- Initialize two pointers
`i`

and`j`

, both set to`0`

. These pointers will traverse`arr1`

and`arr2`

, respectively.

- Initialize two pointers
**Traverse Arrays**:- Use a
`while`

loop to traverse both arrays as long as both pointers are within the bounds of their respective arrays.

- Use a
**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.