# 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); ` `  ``int` `m = ``sizeof``(arr2) / ``sizeof``(arr2); ` `  ``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``); ` `    ``\$m` `= sizeof(``\$arr2``) / sizeof(``\$arr2``); ` `    ``relativeComplement(``\$arr1``, ``\$arr2``, ``\$n``, ``\$m``); ` `    ``return` `0; ` `} ` ` `  `// This code is contributed by nitin mittal ` `?> `

Output :

`6 12 15 `

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Searching complement Arrays Searching

code

load comments