876804. Intersection of Two Sorted Arrays with Distinct Elements
Intersection of Two Sorted Arrays with Distinct Elements
Slug: intersection-of-two-sorted-arrays-with-distinct-elements
Difficulty: Easy
Id: 876804
Topic Tags: Sorting, Arrays
Company Tags: None
Summary
Given two sorted arrays A and B, both containing distinct elements, find their intersection. The intersection of two sets A and B is a set of elements which are present in both A and B.
Detailed Explanation
To solve this problem, we can use the concept of two-pointer technique. Initialize two pointers, one for each array. Start by comparing the elements at these pointers. If the elements are equal, it means that this element is common to both arrays, so add it to our result set and move both pointers forward. If the elements are not equal, move the pointer of the smaller element forward.
Here's a step-by-step breakdown:
- Initialize two pointers
iandj, each pointing to the beginning of arrayAandB, respectively. - Compare the elements at indices
iandj. If they are equal, it means that this element is common to both arrays, so add it to our result set and increment bothiandj. - If the elements are not equal, move the pointer of the smaller element forward. This is because we know that all elements in the intersection must be less than or equal to the maximum element in either array.
- Repeat steps 2-3 until one of the arrays is exhausted.
The time complexity of this algorithm is O(m+n), where m and n are the sizes of the input arrays. The space complexity is O(min(m, n)), as we need to store at most min(m, n) elements in our result set.
Optimized Solutions
Java
public int[] intersection(int[] A, int[] B) {
int i = 0;
int j = 0;
List<Integer> result = new ArrayList<>();
while (i < A.length && j < B.length) {
if (A[i] == B[j]) {
result.add(A[i]);
i++;
j++;
} else if (A[i] < B[j]) {
i++;
} else {
j++;
}
}
int[] arr = new int[result.size()];
for (int k = 0; k < result.size(); k++) {
arr[k] = result.get(k);
}
return arr;
}