Problem statement – Given two sorted arrays, find the intersection (elements present in both arrays).
Clues –
- Solution must be O(M + N) in time and O(min(M, N)) space.
- Can you apply merge sort’s merging logic here?
Solution – This is simple, we can do this in O(M + N) time, where M and N are the array lengths. What we will do here is similar to the “merging” step in merge sort. We will traverse the two sorted arrays simultaneously. Let’s say the first array, A, is indexed by i, and the second array, B, is indexed by j, then,
- A[i] == B[j] – then add it to the intersection.
- A[i] > B[j] – then increment j.
- A[i] < B[j] – then increment i.
In terms of space, it will cost us as much as the size of the intersection, which is minimum of M and N. This isn’t necessarily a tough question, but your impression would take a big blow if you start overthinking this and fail to answer this.
Code –
// Add interesting elements to this collection
ArrayList<Integer> intersection = new ArrayList<>();
int i = 0, j = 0;
while (i != A.length && j != B.length) {
if (A[i] == B[j]) {
// If both are equal, add to intersection
intersection.add(A[i]);
++i;
++j;
} else if (A[i] > B[j]) {
// Increment index to second array
++j;
} else {
// A[i] < B[j]
// Increment index to first array
++i;
}
}
return intersection;
}
[/code]