876771. Intersection of Two Sorted Arrays with Duplicate Elements
Intersection of Two Sorted Arrays with Duplicate Elements
Slug: intersection-of-two-sorted-arrays-with-duplicate-elements
Difficulty: Easy
Topic Tags: Sorting, Arrays
Company Tags: None
Summary
This problem involves finding the intersection of two sorted arrays that may contain duplicate elements. The goal is to return an array containing all the common elements between the two input arrays.
Detailed Explanation
The algorithmic approach for this problem is to iterate through both arrays simultaneously and keep track of the current elements in each array. We can use two pointers, one for each array, starting from the beginning of each array. If the current elements are equal, we add it to our result array and move both pointers forward. If the current element in the first array is smaller, we move the pointer for the first array forward. Similarly, if the current element in the second array is smaller, we move the pointer for the second array forward.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
iandj, to 0, representing the current position in each array. - Compare the elements at positions
iandj. - If the elements are equal, add it to our result array and increment both
iandj. - If the element in the first array is smaller, increment
i. - If the element in the second array is smaller, increment
j. - Repeat steps 2-5 until one of the arrays is exhausted.
The time complexity for this algorithm is O(m + n), where m and n are the lengths of the input arrays. The space complexity is O(min(m, n)), as we need to store the intersection elements in an array.
Optimized Solutions
Java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static int[] intersect(int[] arr1, int[] arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] == arr2[j]) {
if (!result.contains(arr1[i])) {
result.add(arr1[i]);
}
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[result.size()];
for (int k = 0; k < result.size(); k++) {
res[k] = result.get(k);
}
return res;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 3, 4, 6, 7};
int[] result = intersect(arr1, arr2);
for (int i : result) {
System.out.print(i + " ");
}
}
}