Find elements which are present in first array and not in second

Difficulty Level Easy
Frequently asked in Accolite Delhivery Factset Fanatics Snapdeal Zoho
Array HashViews 2980

The problem “Find elements which are present in first array and not in second” states that you are given two arrays. Arrays consist of all the integers. You have to find out the numbers which will not be present in the second array but present in the first array.

Example

Find elements which are present in first array and not in second

a [] = {2,4,3,1,5,6}
b [] = {2,1,5,6}
4 3
a [] ={4,2,6,8,9,5}
b [] ={9,3,2,6,8}
4

Algorithm

  1. Declare a HashSet.
  2. Insert all the elements of array b[] into HashSet.
  3. While i < l1 (length of an array a[]).
    1. If HashSet doesn’t contain array a[i], then print a[i].

Explanation

We have given two integer arrays and a problem statement that asks to find out the number which is present in the first array and not in the second array. We are going to use Hashing in this problem. Hashing helps us to find out the solution in an efficient way.

We are going to put the array b[] numbers in a HashSet and after inserting all the number of array b[]. We are going to traverse array a[] and taking each element at a time and check if HashSet doesn’t contain that element. If it does not have that element, we are going to print that particular element of array a[i] and check for another number.

Let us consider an example and understand this:

First array is a[]=a [] ={2,6,8,9,5,4}, b [] ={9,5,2,6,8}

We have to insert all the elements of array b[] into HashSet, so in HashSet, we have the following values:

HashSet:{9,5,2,6,8} // basically all the values of b[].

We will traverse the array a[] and take each of its elements and check the condition.

i=0, a[i]=2

2 is in the HashSet, so it will not print.

i=1, a[i]=6

6 is in the HashSet, again it will not be printed.

i=2, a[i]=8

8 is in the HashSet, it will not be printed.

i=3, a[i]=9

9 is in the HashSet, so it will not print.

i=4, a[i]=5

5 is in the HashSet, again it will not be printed.

i=5, a[i]=4

4 is not in the HashSet, so this time it will be printed means it is the number which is present in an array a[] but not in array b[] because basically HashSet is the clone of array b[] and our output will become ‘4’.

C++ code to Find elements which are present in first array and not in second

#include<unordered_set>
#include<iostream>
using namespace std;

void getMissingElement(int A[], int B[], int l1, int l2)
{
  unordered_set <int> myset;

  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  for (int j = 0; j < l1; j++)
    if (myset.find(A[j]) == myset.end())
      cout << A[j] << " ";
}
int main()
{
    int a[] = { 9, 2, 3, 1, 4, 5 };
    int b[] = { 2, 4, 1, 9 };
  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);
  getMissingElement(a, b, l1, l2);
  return 0;
}

3 5

Java code to Find elements which are present in first array and not in second

import java.util.HashSet;
import java.util.Set;

class missingElement
{
    public static void getMissingElement(int A[], int B[])
    {
        int l1 = A.length;
        int l2 = B.length;

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < l2; i++)
            set.add(B[i]);

        for (int i = 0; i < l1; i++)
            if (!set.contains(A[i]))
                System.out.print(A[i]+" ");
    }
    public static void main(String []args)
    {
        int a[] = { 9, 2, 3, 1, 4, 5 };
        int b[] = { 2, 4, 1, 9 };

        getMissingElement(a, b);
    }
}

3 5

Complexity Analysis

Time Complexity

O(N) where “N” is the number of elements in the array1. Because using HashSet for insertion and searching allows us to perform these operations in O(1). Thus the time complexity is linear.

Space Complexity

O(N) where “N” is the number of elements in the array1. Since we are storing the elements of the second array. Thus the space required is the same as that of the size of the second array.

Translate »