Difficulty: Medium, Asked-In: Google, Facebook
Key takeaway: An excellent problem to learn time complexity optimization using various approaches. The two-pointer and hash table solutions are intuitive and worth exploring.
Given two unsorted arrays X[] and Y[] of size m and n, write a program to find the intersection of these two arrays.
Example 1
Input: X[] = [3, 4, 6, 2, 8, 5, 9], Y[] = [6, 3, 2, 7, 5, 1]
Output: [3, 6, 2, 5]
Explanation: Common elements are 3, 6, 2, and 5. So the intersection of both arrays is 3, 6, 2, and 5.
Example 2
Input: X[] = [3, 4, 6, 7, 10, 12, 5], Y[] = [7, 11, 18, 15, 12]
Output: [7, 12]
Explanation: Common elements are 7 and 12. So the intersection of both arrays is 7 and 12.
Example 3
Input: X[] = [3, 4, 6, 10, 5], Y[] = [7, 11, 18, 15, 12]
Output: There are no common elements. So the output is an empty array.
A basic idea would be to pick each element from X[] and search linearly in Y[]. We add an element to the output list if it is present in both X[] and Y[].
vector<int> arrayIntersection(int X[], int Y[], int m, int n)
{
vector<int> intersection;
for (int i = 0; i < m; i = i + 1)
{
for (int j = 0; j < n; j = j + 1)
{
if (X[i] == Y[j])
{
intersection.push_back(X[i]);
break;
}
}
}
return intersection;
}
List<Integer> arrayIntersection(int[] X, int[] Y, int m, int n)
{
List<Integer> intersection = new ArrayList<>();
for (int i = 0; i < m; i = i + 1)
{
for (int j = 0; j < n; j = j + 1)
{
if (X[i] == Y[j])
{
intersection.add(X[i]);
break;
}
}
}
return intersection;
}
def arrayIntersection(X, Y, m, n):
intersection = []
for i in range(m):
for j in range(n):
if X[i] == Y[j]:
intersection.append(X[i])
break
return intersection
We are running two nested loops and performing O(1) operations at each iteration. In the worst case, the inner loop will run n times. So the time complexity is O(m) * O(n) * O(1) = O(mn). We are using constant extra space, so the space complexity is O(1). But why are we not considering the output list intersection as part of space complexity? Think!
The critical question is: How can we improve the time complexity of the above approach? Searching is an essential operation in the above code. Can we think of ways to improve the efficiency of searching for element X[i] in Y[]? One idea would be simple: If we sort the array Y[], we can search each element X[i] using binary search. This could help to improve time complexity because binary search takes O(logn) time.
int binarySearch(int Y[], int n, int target)
{
int l = 0, r = n;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (Y[mid] == target)
return mid;
else if (Y[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
vector<int> arrayIntersection(int X[], int Y[], int m, int n)
{
vector<int> intersection;
sort(Y, Y + n); // sort the array Y
for (int i = 0; i < m; i = i + 1)
{
if (binarySearch(Y, n, X[i]) != -1)
intersection.push_back(X[i]);
}
return intersection;
}
int binarySearch(int[] Y, int n, int target)
{
int l = 0, r = n;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (Y[mid] == target)
return mid;
else if (Y[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
Vector<Integer> arrayIntersection(int[] X, int[] Y, int m, int n)
{
Vector<Integer> intersection = new Vector<Integer>();
Arrays.sort(Y); // sort the array Y
for (int i = 0; i < m; i = i + 1)
{
if (binarySearch(Y, n, X[i]) != -1)
intersection.add(X[i]);
}
return intersection;
}
def binarySearch(Y: List[int], n: int, target: int) -> int:
l, r = 0, n
while l <= r:
mid = l + (r - l) // 2
if Y[mid] = target:
return mid
elif Y[mid] > target:
r = mid - 1
else:
l = mid + 1
return -1
def arrayIntersection(X: List[int], Y: List[int], m: int, n: int) -> List[int]:
intersection = []
Y = sorted(Y) # sort the array Y
for i in range(m):
if binarySearch(Y, n, X[i]) != -1:
intersection.append(X[i])
return intersection
We are using heap sort and iterative binary search for the implementation. The time complexity is the time complexity of sorting array Y[] using heap sort plus the time complexity of searching for each element X[i] in Y[] using binary search. This gives us O(nlogn) + m * O(logn) = O(nlogn + mlogn). If m > n, then mlogn > nlogn, and the time complexity would be O(mlogn).
The space complexity is the space complexity of heap sort plus the space complexity of the iterative binary search, which is O(1) + O(1) = O(1). What would be the space complexity if we use merge sort and recursive binary search for the implementation? Think!
In the above approach, the overall time complexity of searching is O(mlogn). The critical question is: Can we improve the time complexity of searching further? Here's an idea: If we sort both arrays, we can apply the two-pointers approach, similar to the merging procedure of merge sort, to find common elements. Think!
After sorting both arrays, the idea would be to start comparing one element of X[] with one element of Y[]. If both are equal, we add them to the output list and move to the next elements in both arrays. Otherwise, we move to the next element in the array that includes the smaller element. Think!
Now we run a loop while i < m and j < n:
vector<int> arrayIntersection(int X[], int Y[], int m, int n)
{
vector<int> intersection;
sort(X, X + m);
sort(Y, Y + n);
int i = 0, j = 0;
while (i < m && j < n)
{
if (X[i] == Y[j])
{
intersection.push_back(X[i]);
i = i + 1;
j = j + 1;
}
else if (X[i] < Y[j])
i = i + 1;
else
j = j + 1;
}
return intersection;
}
List<Integer> arrayIntersection(int[] X, int[] Y, int m, int n)
{
List<Integer> intersection = new ArrayList<>();
Arrays.sort(X);
Arrays.sort(Y);
int i = 0, j = 0;
while (i < m && j < n)
{
if (X[i] == Y[j])
{
intersection.add(X[i]);
i = i + 1;
j = j + 1;
}
else if (X[i] < Y[j])
i = i + 1;
else
j = j + 1;
}
return intersection;
}
def arrayIntersection(X: List[int], Y: List[int], m: int, n: int) -> List[int]:
intersection = []
X.sort()
Y.sort()
i, j = 0, 0
while i < m and j < n:
if X[i] == Y[j]:
intersection.append(X[i])
i = i + 1
j = j + 1
elif X[i] < Y[j]:
i = i + 1
else:
j = j + 1
return intersection
Suppose we are using heap sort for the implementation.
For m > n, if we compare the time complexity of this approach with the previous approach, then it is not better! The idea is: We have improved the time complexity of searching after sorting both arrays, but here, the time complexity is dominated by the sorting algorithm, which is O(mlogm). The time complexity of the above approach is O(mlogn), which is better than O(mlogm). Think!
We can improve the time complexity of searching further using a hash table because it can perform searching in O(1) time on average. The idea is to insert all elements of Y[] into the hash table and search for each element X[i]. If element X[i] is present in the hash table, we add it to the output list.
vector<int> arrayIntersection(int X[], int Y[], int m, int n)
{
vector<int> intersection;
unordered_set<int> H;
for (int i = 0; i < n; i = i + 1)
H.insert(Y[i]);
for (int i = 0; i < m; i = i + 1)
{
if (H.count(X[i]))
intersection.push_back(X[i]);
}
return intersection;
}
List<Integer> arrayIntersection(int[] X, int[] Y, int m, int n)
{
List<Integer> intersection = new ArrayList<>();
HashSet<Integer> H = new HashSet<>();
for (int i = 0; i < n; i = i + 1)
H.add(Y[i]);
for (int i = 0; i < m; i = i + 1)
{
if (H.contains(X[i]))
intersection.add(X[i]);
}
return intersection;
}
def arrayIntersection(X: List[int], Y: List[int], m: int, n: int) -> List[int]:
intersection = []
H = set()
for i in range(n):
H.add(Y[i])
for i in range(m):
if X[i] in H:
intersection.append(X[i])
return intersection
Time complexity = Time complexity of inserting n elements of Y[] in hash table + Time complexity of searching m elements of X[] in hash table = n * O(1) + m * O(1)) = O(m + n). Space complexity = O(n), for storing values in hash table.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!