876770. Intersection of Two arrays with Duplicate Elements
Easy
Intersection of Two arrays with Duplicate Elements
Slug: intersection-of-two-arrays-with-duplicate-elements
Difficulty: Easy
Id: 876770
Topic Tags: Sorting, two-pointer-algorithm, Arrays, Hash
Company Tags: None
Summary
Given two arrays A and B, the task is to find all elements that are present in both arrays. The arrays can contain duplicate elements. This problem involves sorting and using a two-pointer algorithm.
Detailed Explanation
To solve this problem, we can use the following approach:
- First, sort both arrays in ascending order.
- Initialize two pointers,
iandj, to point to the start of each array. - Compare the elements at positions
iandj. If they are equal, it means that we have found an element that is present in both arrays, so add this element to our result set. - Move the pointer that points to the smaller element one step forward. This is because all elements to the left of the current position will be less than or equal to the current element, and all elements to the right will be greater.
- Repeat steps 3 and 4 until we have processed all elements in both arrays.
Here's a step-by-step breakdown:
A = [1, 2, 2, 3]
B = [2, 2]
Result:
[2, 2]
In this example, the result is [2, 2] because these are the elements that are present in both arrays.
Time complexity: O(n log n) due to sorting.
Space complexity: O(m + n) for storing the result set, where m and n are the sizes of the input arrays.
Optimized Solutions
Java
import java.util.*;
public class Main {
public static List<Integer> findIntersection(int[] A, int[] B) {
Arrays.sort(A);
Arrays.sort(B);
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
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++;
}
}
return result;
}
public static void main(String[] args) {
int[] A = {1, 2, 2, 3};
int[] B = {2, 2};
List<Integer> result = findIntersection(A, B);
System.out.println(result);
}
}