Searching: Find the missing elements of 2 sorted arrays

Problem Statement:

You are given 2 sorted arrays of different size.
You need to find the elements that are present in array 1 but not in array 2.

Example:

Input:

a = [1, 2, 3, 4, 5, 6, 7, 8]

b = [1, 2, 3, 4, 5, 6]

Output: 7, 8

Solution 1: Two pointer solution

Take 2 pointers i and j pointing to both of the arrays.

If a[i] is smaller than b[j], the print the element and increment i.

If a[i] element is greater than b[j], increment j.

else increment both j and i.

Time Complexity: O(m + n)
Space Complexity: O(1)

Solution 2:

Store the elements of second array into a set

Traverse the first array and for each index, search in the set if its not present add in the result array.

Time Complexity: O(x) // x is the size of the larger array
Space Complexity: O(m) // to store the elements in set

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;


void solution_1 (int arr1[], int arr2[], int n, int m) 

{
 
  int i = 0, j = 0;
  while (i < n && j < m) 
  {
 
    if (arr1[i] < arr2[j]) 
    {
      cout << arr1[i] << " ";
      i++;
 
    } 
    else if (arr1[i] > arr2[j]) 
    {
      j++;
 
    } 
    else if (arr1[i] == arr2[j]) 
    {
      i++;
      j++;
    }
  }
 
  while (i < n) 
    cout << arr1[i] << " ";  
}

 
void solution_2 (int arr1[], int arr2[], int n, int m)
{

    unordered_set<int> s;

    vector<int> ans;

    for (int i = 0; i < m; i++)
        s.insert(arr2[i]);

    for (int i = 0; i < n; i++) 
    {

        if (s.find(arr1[i]) == s.end())
            ans.push_back(arr1[i]);
    }

    for (auto x : ans)
        cout << x << " ";
}

 
int main() 
{
  int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8};
  int arr2[] = {1, 2, 3, 4, 5, 6, 8};
  
  int n = sizeof(arr1) / sizeof(arr1[0]);
  int m = sizeof(arr2) / sizeof(arr2[0]);

  solution_1 (arr1, arr2, n, m);
  cout<<endl;
  solution_2 (arr1, arr2, n, m);

  return 0;
}

Output

7
7