Tutorialspoint.dev

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


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 <iostream>
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

<?php
// PHP program to find all those 
// elements of arr1[] that are not
// present in arr2[]
  
function relativeComplement($arr1, $arr2,
                                 $n, $m)
{
  
    $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])
        {
            echo $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
        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 


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter