**Simple and Brute-force approach**

Method#1:

Method#1:

Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

**Better approach with binary search**

Method#2:

Method#2:

This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

**Efficient**

Method#3:

Method#3:

This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

#include <iostream> #include <string> #include <vector> using namespace std; //prints the intersection of two sorted arrays //duplicates are allowed void printIntersect(vector<int>& s1, vector<int>& s2) { //i and j start 0 i.e first element int i = 0 , j= 0; //while either of the two indices reaches end while ( i < s1.size() && j < s2.size() ) { //if first array element is lesser, advance that index by one if( s1[i] < s2[j] ) { i++; } //otherwise advance second index else if( s1[i] > s2[j] ) { j++; } //both elements are same, print it, and advance both the pointers else { cout<<s1[i]<<" "; i++; j++; } } } int main() { vector<int> set1, set2; int n1,n2; //size of the sets cin>>n1>>n2; int i; //read two arrays for( i = 0 ; i < n1; i++ ) { int d; cin>>d; set1.push_back(d); } for( i = 0 ; i < n2; i++ ) { int d; cin>>d; set2.push_back(d); } printIntersect(set1,set2); return 0; }