876745. Union of Two Sorted Arrays with Distinct Elements
Union of Two Sorted Arrays with Distinct Elements
Slug: union-of-two-sorted-arrays-with-distinct-elements Difficulty: Easy Id: 876745 Topic Tags: Arrays
Summary
Given two sorted arrays, we need to find their union. The union is the set of elements that are present in either array or both. We can assume that there are no duplicates in each array and the arrays do not contain duplicate elements.
Detailed Explanation
To solve this problem, we will iterate through both arrays simultaneously. Since they are sorted, if the current element of one array is less than the current element of the other array, it means all remaining elements in the first array are less than any element in the second array. So, we can add all these elements to our result set.
Here's a step-by-step breakdown of the solution:
- Initialize an empty array
resultto store the union. - Initialize two pointers,
iandj, to point to the first elements of each array. - Compare the current elements at positions
iandj.- If the elements are equal, add this element to the result set and increment both
iandj. - If the element in the first array is less than the element in the second array, add all remaining elements from the first array to the result set and increment
i. This is because we know that any remaining elements in the first array are less than any element in the second array. - If the element in the second array is less than the element in the first array, add all remaining elements from the second array to the result set and increment
j.
- If the elements are equal, add this element to the result set and increment both
- Repeat step 3 until one of the arrays is exhausted.
The time complexity of this solution is O(m + n), where m and n are the sizes of the two input arrays. The space complexity is O(m + n) for storing the union.
Optimized Solutions
Java
import java.util.*;
public class Main {
public static int[] union(int[] arr1, int[] arr2) {
int i = 0, j = 0;
int[] result = new int[arr1.length + arr2.length];
int k = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] == arr2[j]) {
result[k++] = arr1[i++];
j++;
} else if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
while (i < arr1.length) {
result[k++] = arr1[i++];
}
while (j < arr2.length) {
result[k++] = arr2[j++];
}
return Arrays.copyOf(result, k);
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};
int[] unionArr = union(arr1, arr2);
for (int i : unionArr) {
System.out.print(i + " ");
}
}
}