About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Intersection Of Arrays Problem

Problem Statement:

Given two sorted arrays (sorted in non descending order) as input, you need to complete the function intersectionOfArrays which will return a new array containing elements that are present in both of the input arrays which is basically what intersection of array means.

The input arrays may have duplicate entries, but the returned array should be free of duplicates. In case of no common element, add -1 in the list to be returned as function output.

Input Format:

There are two arguments in input. The first argument will be integer array 1 and the second argument will be integer array 2.

Output Format:

Return an integer array representing intersection of given input arrays.

Constraints:

● 1

● 0

● Order of elements in returned array does not matter.

Sample Input:

arr1 = [2, 3, 3, 5, 5, 6, 7, 7, 8, 12], arr2 = [5, 5, 6, 8, 8, 9, 10, 10]

Sample Output:

result = [5, 6, 8]

As 5, 6, 8 are the elements which are common between both arr1 and arr2 and as problem demands not to return duplicates in returned array hence result array is [5, 6, 8]. [5, 8, 6] + all other permutations will be considered as valid answer.

Solution

We have provided a solution which contains necessary comments to understand the approach used:

1. binary_search_solution.java

Description:

As we are given two arrays arr1 and arr2, we need to return result array containing common elements from arr1 and arr2.

A simple brute force approach can be to iterate over any one array and check whether that element is present in arr2 or not. If present and that element is not already added to the result array, we will add that element in the result array. Once done with iteration we return result array. This approach will take O(n^2) time as in one loop we will iterate and our condition will take O(n) to check whether an element is present in an array or not.

We can optimise above mentioned solution with the help of binary search. As we know both the given arrays are sorted in non ascending order we can use binary search instead of linear search to optimise our approach.

For better understanding, please have a look at the solution.

Time Complexity:

O(min(n, m)*log(max(n, m))) where n denotes the size of arr1 and m denotes the size of arr2.

As we are iterating over the array which is smaller in size that will take O(min(n, m)) and doing binary search on array which is larger in size that will take O(log(max(n, m))) hence total complexity will be O(min(n, m)*log(max(n, m))).

Auxiliary Space Used:

O(1).

We are not storing anything extra.

Space Complexity:

O(n+m) where n denotes the size of arr1 and m denotes the size of arr2.

To read input it will take O(n+m) as we are reading two arrays of size n and m respectively, auxiliary space used is O(1) and to store output it will take O(min(n, m)) hence total space complexity will be O(n+m) + O(1) + O(min(n+m)) → O(n+m).

2. hashing_solution.java

Description:

In this solution we will use hashing. We will store any one of the arrays in hashset and use same algorithm as used above for binary_search_solution but instead of using binary search to check whether element contains in other array or not we will use hash set lookup which will be more optimised.

Time Complexity:

O(n+m) where n denotes the size of arr1 and m denotes the size of arr2.

As we are going to add any one arrays elements in set and iterate over other which will take O(n) and O(m) time complexity respectively hence total complexity will be O(n+m).

Auxiliary Space Used:

O(min(n, m)) where n denotes the size of arr1 and m denotes the size of arr2.

As we are storing elements of smaller array in set hence it will take O(min(n, m)) extra space.

Space Complexity:

O(n+m) where n denotes the size of arr1 and m denotes the size of arr2.

To read input it will take O(n+m) space and auxiliary space used is O(min(n, m)) and to store output it will take O(min(n, m)) hence total space complexity will be O(n+m) + O(min(n, m)) + O(min(n, m)) → O(n+m).

3. solution.java

Description:

In this solution, we are going to fully leverage the condition that both arrays are sorted in non descending order hence we are going to iterate over both the arrays simultaneously and maintain two pointers i and j.

1. If arr1[i] < arr2[j], we will increment pointer of arr1 i.e. i.

2. If arr1[i] > arr2[j], we will increment pointer of arr2 i.e. j.

3. If arr1[i] == arr2[j]

a. We check whether the current value is not already covered in result array to avoid duplicates and add that in result array.

b. We will increment both pointers i and j.

4. We continue this until we reach at the end of any one of the arrays.

Time Complexity:

O(min(n, m)) where n denotes the size of arr1 and m denotes the size of arr2.

As we are iterating over both the arrays simultaneously and we iterate till we reach the end of any one array hence time complexity will be O(min(n, m)).

Auxiliary Space Used:

O(1).

We are not storing anything extra.

Space Complexity:

O(n+m) where n denotes the size of arr1 and m denotes the size of arr2.

To read input it will take O(n+m) space and auxiliary space used is O(1) and to store output it will take O(min(n, m)) hence total space complexity will be O(n+m) + O(1) + O(min(n, m)) → O(n+m).