# Find relative complement of two sorted arrays

Given two sorted arrays arr1 and arr2 of size m and n respectively. We need to find relative complement of two array i.e, arr1 – arr2 which means that we need to find all those elements which are present in arr1 but not in arr2.

Examples:

Input : arr1[] = {3, 6, 10, 12, 15}
arr2[] = {1, 3, 5, 10, 16}
Output : 6 12 15
The elements 6, 12 and 15 are present
in arr[], but not present in arr2[]

Input : arr1[] = {10, 20, 36, 59}
arr2[] = {5, 10, 15, 59}
Output : 20 36

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

1. Take two pointers i and j which traverse through arr1 and arr2 respectively.
2. If arr1[i] element is smaller than arr2[j] element print this element and increment i.
3. If arr1 element is greater than arr2[j] element then increment j.
4. otherwise increment i and j.

## C++

 // CPP program to find all those  // elements of arr1[] that are not // present in arr2[] #include using namespace std;    void relativeComplement(int arr1[], int arr2[],                                int n, int m) {      int i = 0, j = 0;   while (i < n && j < m) {        // If current element in arr2[] is     // greater, then arr1[i] can't be      // present in arr2[j..m-1]     if (arr1[i] < arr2[j]) {       cout << arr1[i] << " ";       i++;        // Skipping smaller elements of     // arr2[]     } else if (arr1[i] > arr2[j]) {       j++;        // Equal elements found (skipping     // in both arrays)     } else if (arr1[i] == arr2[j]) {       i++;       j++;     }   }      // Printing remaining elements of   // arr1[]   while (i < n)      cout << arr1[i] << " ";   }    // Driver code int main() {   int arr1[] = {3, 6, 10, 12, 15};   int arr2[] = {1, 3, 5, 10, 16};   int n = sizeof(arr1) / sizeof(arr1[0]);   int m = sizeof(arr2) / sizeof(arr2[0]);   relativeComplement(arr1, arr2, n, m);   return 0; }

## Java

 // Java program to find all those  // elements of arr1[] that are not // present in arr2[]    class GFG {     static void relativeComplement(int arr1[], int arr2[],                                              int n, int m)      {                int i = 0, j = 0;         while (i < n && j < m)          {                        // If current element in arr2[] is             // greater, then arr1[i] can't be              // present in arr2[j..m-1]             if (arr1[i] < arr2[j])              {                 System.out.print(arr1[i] + " ");                 i++;                        // Skipping smaller elements of             // arr2[]             } else if (arr1[i] > arr2[j])              {                 j++;                        // Equal elements found (skipping             // in both arrays)             }              else if (arr1[i] == arr2[j])              {                 i++;                 j++;             }         }                    // Printing remaining elements of         // arr1[]         while (i < n)              System.out.print(arr1[i] + " ");      }            // Driver code     public static void main (String[] args)      {         int arr1[] = {3, 6, 10, 12, 15};         int arr2[] = {1, 3, 5, 10, 16};         int n = arr1.length;         int m = arr2.length;         relativeComplement(arr1, arr2, n, m);      } }    // This code is contributed by Anant Agarwal.

## Python3

 # Python program to find all those  # elements of arr1[] that are not # present in arr2[]    def relativeComplement(arr1, arr2, n, m):         i = 0     j = 0     while (i < n and j < m):             # If current element in arr2[] is         # greater, then arr1[i] can't be          # present in arr2[j..m-1]         if (arr1[i] < arr2[j]):             print(arr1[i] , " ", end="")             i += 1                 # Skipping smaller elements of             # arr2[]         elif (arr1[i] > arr2[j]):             j += 1                 # Equal elements found (skipping             # in both arrays)         elif (arr1[i] == arr2[j]):             i += 1             j += 1            # Printing remaining elements of     # arr1[]     while (i < n):          print(arr1[i] , " ", end="")     # Driver code arr1= [3, 6, 10, 12, 15] arr2 = [1, 3, 5, 10, 16] n = len(arr1) m = len(arr2) relativeComplement(arr1, arr2, n, m)    # This code is contributed # by Anant Agarwal.

## C#

 // C# program to find all those  // elements of arr1[] that are not // present in arr2[] using System;    namespace Complement {     public class GFG     {                                 static void relativeComplement(int []arr1, int []arr2,                                                    int n, int m)         {                int i = 0, j = 0;         while (i < n && j < m)          {                        // If current element in arr2[] is             // greater, then arr1[i] can't be              // present in arr2[j..m-1]             if (arr1[i] < arr2[j])              {                 Console.Write(arr1[i] + " ");                 i++;                        // Skipping smaller elements of             // arr2[]             } else if (arr1[i] > arr2[j])              {                 j++;                        // Equal elements found (skipping             // in both arrays)             }              else if (arr1[i] == arr2[j])              {                 i++;                 j++;             }         }                    // Printing remaining elements of         // arr1[]         while (i < n)              Console.Write(arr1[i] + " ");      }            // Driver code     public static void Main()     {         int []arr1 = {3, 6, 10, 12, 15};         int []arr2 = {1, 3, 5, 10, 16};         int n = arr1.Length;         int m = arr2.Length;         relativeComplement(arr1,arr2, n, m);     }     } }    // This code is contributed by Sam007

## PHP

 \$arr2[\$j])          {             \$j++;                        // Equal elements found (skipping             // in both arrays)         }          else if (\$arr1[\$i] == \$arr2[\$j])         {             \$i++;             \$j++;         }     }        // Printing remaining elements of     // arr1[]     while (\$i < \$n)          echo \$arr1[\$i] , " ";  }    // Driver code {     \$arr1 = array(3, 6, 10, 12, 15);     \$arr2 = array(1, 3, 5, 10, 16);     \$n = sizeof(\$arr1) / sizeof(\$arr1[0]);     \$m = sizeof(\$arr2) / sizeof(\$arr2[0]);     relativeComplement(\$arr1, \$arr2, \$n, \$m);     return 0; }    // This code is contributed by nitin mittal ?>

Output :

6 12 15

## tags:

Arrays Searching complement Arrays Searching