Intersection of two sorted arrays

Problem Statement: Find the intersection of two sorted arrays. OR in other words, Given 2 sorted arrays, find all the elements which occur in both the arrays.

Examples:

Example 1:
Input: 
A: [1 2 3 3 4 5 6]
, B: [3 3 5]
Output: 3,3,5
Explanation: We are given two arrays A and B. 
The elements present in both the arrays  
are 3,3 and 5.

Example 2:
Input: 
A: [1 2 3 3 4 5 6]
, B: [3 5]
Output: 3,5
Explanation: We are given two arrays A and B. 
The elements present in both the arrays are 3 and 5.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach:

For a brute force approach, we are given 2 arrays, what we can do is take the element from array A and search if it is present in array B.

For Example:

A: [1 2 3 3 4 5 6] 
B: [3 3 5]

Here, we will first pick 1 which is the first element of array A, and check it in array B. Now, since we know that the array is sorted, if we find an element in array B greater than the current element, we do not check any further. So we break the loop at the first element itself. The same thing happens with 2. 

Now when we reach 3, we check if 3 exists in the second array, yes it does, push it to and. we can break here because we have found 3, so no need to move further. Now the next 3 comes, we check it with the first element of array B, now it matches again, but that first element had already been matched to the previous 3.

Now, this is an issue. To solve this, we take a visited array. the array is [0,0,0] initially. And when we match any element and push it to ans, we mark it as visited [1,0,0]. Now the current 3 when matched with the first 3 of the array checks if it is unvisited, if not it moves further. Gets matched with the next 3, gets pushed in ans, and the loop continues, till the length of the whole array A.

Code:

C++ Code


#include<bits/stdc++.h>

using namespace std;

int main() {
  vector < int > A {1,2,3,3,4,5,6,7};
  vector < int > B {3,3,4,4,5,8};

  vector < int > ans;
  vector < int > visited(B.size(), 0); // to maintain visited 
  int i = 0, j = 0;
  for (i = 0; i < A.size(); i++) {
    for (j = 0; j < B.size(); j++) {

      if (A[i] == B[j] && visited[j] == 0) { 
      //if element matches and has not been matched with any other before
        ans.push_back(B[j]);
        visited[j] = 1;

        break;
      } else if (B[j] > A[i]) break; 
        //because array is sorted , element will not be beyond this
    }
  }
  cout<<"The elements are: ";
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }

  return 0;
}

Output:

The elements are: 3 3 4 5

Time Complexity: O(n2)

Space Complexity: O(n) for the extra visited vector

Java Code

import java.util.*;

class TUF{
public static void main(String args[]) 
{
  int A[]= {1,2,3,3,4,5,6,7};
  int B[]= {3,3,4,4,5,8};

  ArrayList<Integer> ans=new ArrayList<>();
  int visited[]=new int[B.length]; // to maintain visited 
  int i = 0, j = 0;
  for (i = 0; i < A.length; i++) {
    for (j = 0; j < B.length; j++) {

      if (A[i] == B[j] && visited[j] == 0) { 
     //if element matches and has not been matched with any other before
        ans.add(B[j]);
        visited[j] = 1;

        break;
      } else if (B[j] > A[i]) break; 
       //because array is sorted , element will not be beyond this
    }
  }
  System.out.print("The elements are: ");
  for (i = 0; i < ans.size(); i++) {
    System.out.print(ans.get(i)+" ");
  }
}
}

Output:

The elements are: 3 3 4 5

Time Complexity: O(n2)

Space Complexity: O(n) for the extra visited vector

Solution 2: 2 Pointer approach

As we saw in the brute force, we were not going forward as soon as we encountered any element greater than the element we are looking for. That fact, about arrays being sorted, can be used to solve this problem in one pass.

Initialize 2 pointers i and j. i=0 and will iterate over Array A, j=0 and will iterate over Array B.

Now A[i] is less than B[j], so we are certainly not going to find A[i],i.e,1 any further in the array. Let’s increment the pointer i and check the next element.

Again A[i] is less than B[j], so we are certainly not going to find A[i],i.e,2 any further in the array. Let’s increment the pointer i and check the next element.

Now, A[i] and B[j] is a match, so push A[i] into the ans vector. And this time we move both i and j.

Now, A[i] and B[j] is a match, so push A[i] into the ans vector. And this time we move both i and j. Since we are moving both i and j upon encountering a match, there is no way that the same element matches duplicate elements in the other array.

Again A[i] is less than B[j], so we are certainly not going to find A[i],i.e,4 any further in the array. Let’s increment the pointer i and check the next element.

Now, A[i] and B[j] is a match, so push A[i] into the ans vector. And this time we move both i and j. Now when we move j, it goes out of bounds, which means we have traversed the array fully, and there are no elements left to be matched with array A, so we stop here.

Just to make the other case clear as well, if A[i] > B[j],i.e, all elements in A are greater than the current element in B, we move the j pointer. And the loop continues till either array A or B exists.

Code:

C++ Code


#include<bits/stdc++.h>

using namespace std;

int main() {
  vector < int > A {1,2,3,3,4,5,6,7};
  vector < int > B {3,3,4,4,5,8};

   vector < int > ans;

  int i = 0, j = 0; // to traverse the arrays

  while (i < A.size() && j < B.size()) {
    if (A[i] < B[j]) { //if current element in i is smaller
      i++;
    } else if (B[j] < A[i]) {
      j++;
    } else {
      ans.push_back(A[i]); //both elements are equal
      i++;
      j++;
    }
  }
  cout<<"The elements are: ";
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }

  return 0;
}

output:

The elements are: 3 3 4 5

Time Complexity: O(n) n being the min length of the 2 arrays.

Space Complexity: O(1)

Java Code

import java.util.*;

class TUF{
public static void main(String args[]) {
  int A[]={1,2,3,3,4,5,6,7};
  int B[]= {3,3,4,4,5,8};

  ArrayList<Integer> ans=new ArrayList<>();

  int i = 0, j = 0; // to traverse the arrays

  while (i < A.length && j < B.length) {
    if (A[i] < B[j]) { //if current element in i is smaller
      i++;
    } else if (B[j] < A[i]) {
      j++;
    } else {
      ans.add(A[i]); //both elements are equal
      i++;
      j++;
    }
  }
  System.out.print("The elements are: ");
  for (i = 0; i < ans.size(); i++) {
    System.out.print(ans.get(i)+" ");
  }
}
}

output:

The elements are: 3 3 4 5

Time Complexity: O(n) n being the min length of the 2 arrays.

Space Complexity: O(1)

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article