Find the Difference of Two Arrays

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

1. answer[0] is a list of all distinct integers in nums1 which are not present in nums2.

2. answer[1] is a list of all distinct integers nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

 

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Approach

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class DiffTwoArray {
    public static void main(String[] args) {

        int nums1[] = { 1, 2, 3 }, nums2[] = { 2, 4, 6 };

        System.out.println(findDifference(nums1, nums2));

    }

    public static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {

        // creating the sets
        Set<Integer> st1 = new HashSet<Integer>();
        Set<Integer> st2 = new HashSet<Integer>();

        // add all the elements of first arrays into the set 1
        for (int i = 0; i < nums1.length; i++) {
            st1.add(nums1[i]);
        }

        // add all the elements of second arrays into the set 2
        for (int i = 0; i < nums2.length; i++) {
            st2.add(nums2[i]);
        }

        // remove the element which present in the set 1 and from array 2
        for (int i = 0; i < nums2.length; i++) {
            if (st1.contains(nums2[i]))
                st1.remove(nums2[i]);
        }

        // remove the element which present in the set 2 and from array 1
        for (int i = 0; i < nums1.length; i++) {
            if (st2.contains(nums1[i]))
                st2.remove(nums1[i]);
        }

        // creating the lists
        List<Integer> answer1 = new ArrayList<Integer>();

        List<Integer> answer2 = new ArrayList<Integer>();

        Iterator<Integer> value1 = st1.iterator();
        // add the set 1 element into list 1
        while (value1.hasNext()) {
            answer1.add(value1.next());
        }

        Iterator<Integer> value2 = st2.iterator();

        // add the set 1 element into list 1
        while (value2.hasNext()) {
            answer2.add(value2.next());
        }

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // add both the list into one list
        result.add(answer1);
        result.add(answer2);

        // return the final list
        return result;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2)
{
    set<int> st1, st2;

    // insert the first array elements into set 1
    for (int i = 0; i < nums1.size(); i++)
    {

        st1.insert(nums1[i]);
    }

    // insert the second array elements into set 2
    for (int i = 0; i < nums2.size(); i++)
    {
        st2.insert(nums2[i]);
    }

    // remove the element from set 1 which present in second array
    for (int i = 0; i < nums2.size(); i++)
    {
        if (st1.find(nums2[i]) != st1.end())
            st1.erase(nums2[i]);
    }

    // remove the element from set 2 which present in first array
    for (int i = 0; i < nums1.size(); i++)
    {
        if (st2.find(nums1[i]) != st2.end())
            st2.erase(nums1[i]);
    }

    vector<int> answer1, answer2;
    for (auto it = st1.begin(); it != st1.end(); ++it)
    {
        answer1.push_back(*it);
    }

    for (auto it = st2.begin(); it != st2.end(); ++it)
    {
        answer2.push_back(*it);
    }

    vector<vector<int>> result;
    result.push_back(answer1);
    result.push_back(answer2);

    return result;
}
int main()
{
    vector<int> nums1 = {1, 2, 3}, nums2 = {2, 4, 6};

    vector<vector<int>> result = findDifference(nums1, nums2);

    cout << "[";
    for (int i = 0; i < result.size(); i++)
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j];
            if (j != result[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if (i != result.size() - 1)
            cout << ",";
    }
    cout << "]";
}

Output:

[[1, 3], [4, 6]]

set upper_bound() in C++

upper_bound(): This is a build-in function in STL. This function finds the end of a 

subsequence matching is given key.  

This function returns an iterator pointing to the first element greater than key, 

or end().

Parameters: One Parameter is required for this function.

__x – Key to being located. 

Syntax:

set<data_type>::iterator it = st.upper_bound(__x)

For Example:

st = {1,2,6,8}

st.upper_bound(4) = > It returns 6.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({6, 2, 1, 8});

    set<int>::iterator it = st.upper_bound(4);

    cout << *it << "\n";

    return 0;
}

set swap() in C++

swap(): This is a build-in function in STL. This function swaps values of two sets.

Parameters: One parameter is required for this function.

__l: A set of elements of the same type value.

Syntax:

st.swap(__l)

For Example:

st = {1,2,3,4}

st1= {5,6,7,10,11}

st.swap(st1) = > st = {5,6,7,10,11}, st1 = {1,2,3,4}

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 2, 4, 3});

    set<int> st1;
    st1.insert({5, 6, 7, 10, 11});
    st.swap(st1);

    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << " ";
    cout << "\n";

    for (auto it = st1.begin(); it != st1.end(); it++)
        cout << *it << " ";
   
    return 0;
}

set size() in C++

size(): This function returns the size of the set. 

This function is available in the below file.

File: stl_set.h

Parameters: No parameters are required for this function.

Syntax:

st.size()

For Example:

st = {1,2,3,4}

st.size() = > It returns 4.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 3, 4, 2});

    cout << st.size() << "\n";

    return 0;
}

set rend() in C++

rend(): This is a build-in function in STL. This function returns a read-only 

(constant) reverse iterator that points to the last pair in the set.

Note: Iteration is done in descending order according to the keys. 

This function is available in the below file.

File: stl_set.h

Parameters: No parameters are required for this function.

Syntax:

set<data_type>::const_reverse_iterator it = st.rend()

For Example:

st = {1,2,3,4}

st.rend() = > It returns an iterator that points to last element (i.e 4)

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 4, 3, 2});

    set<int>::const_reverse_iterator it = st.rend();

    cout << *it << "\n";

    return 0;
}

set rbegin() in C++

rbegin(): This is a build-in function in STL. This function returns a read-only 

(constant) iterator that points to the last element in the set.

Note: Iteration is done in descending order according to the keys. 

This is available in the below file.

File: stl_set.h

Parameters: No parameters are required for this function.

Syntax:

set<data_type>::const_reverse_iterator it = st.rbegin()

For Example:

st = {1,2,3,4}

st.rbegin() = > It points to 4.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 4, 3, 2});

    set<int>::const_reverse_iterator it = st.rbegin();

    cout << *it << "\n";
  
    return 0;
}

set operator = in C++

operator =: This is an operator to assign values. Set list assignment operator.

Parameters:

 __l – An initializer_list. 

This function fills a set with copies of the elements in the initializer list __l. 

Note that the assignment completely changes the set and that the resulting set's size is the 

same as the number of elements assigned.

Syntax:

st = {__l}

For Example:

st ={3,2,1,4}

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;

    st = {3, 2, 1, 4};

    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << " ";

    return 0;
}

set max_size() in C++

max_size(): This is a build-in function in STL. This function returns the maximum 

size of the set. 

This function is available in the below file.

File: stl_set.h

Parameters: No parameters are required for this function.

Syntax:

st.max_size()

For Example:

st = {1,2,3,4}

st.max_size() = > It returns max_size (i.e 461168601842738790)

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 2, 4, 3});

    cout << st.max_size() << "\n";

    return 0;
}

set lower_bound() in C++

lower_bound(): This is a build-in function in STL. This function finds the beginning of a subsequence matching given key. This function returns an iterator pointing to the first element

equal to or greater than key, or end(). 

This function returns the first element of a subsequence of elements that match the given key. If unsuccessful it returns an iterator pointing to the first element that has a greater value than the given key or end() if no such element exists.

Parameters: One parameter is required for this function.

 __x – Key to being located. 

Syntax:

set<data_type>::iterator it = st.lower_bound(__x)

For Example:

st = {1,19,5,2}

st.lower_bound(3) = > It returns iterator pointing to 5.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> st;
    st.insert({1, 19, 5, 2});

    set<int>::iterator it = st.lower_bound(3);

    cout << *it << "\n";

    return 0;
}