Last Updated on July 5, 2023 by Mayank Dham
The union and intersection of two sorted arrays are important operations when working with arrays in programming. These operations allow us to combine or find common elements between two arrays while maintaining the sorted order. In this article, we will explore how to implement the union and intersection operations on two sorted arrays using the C programming language. By understanding the concepts and studying code examples, readers will gain the knowledge necessary to perform efficient union and intersection operations in their own C programs.
The union of two arrays results in a new array that contains all the distinct elements from both arrays, while the intersection of two arrays yields a new array that contains only the common elements between the two arrays. These operations are particularly useful in various scenarios, such as merging data sets, finding common elements in datasets, or eliminating duplicates from multiple arrays.
What is Union and Intersection of the Two Sorted Arrays in C?
The union and intersection are fundamental operations performed on two sorted arrays to combine or find common elements between them, respectively. Here’s a brief explanation of each operation:
Union of Two Sorted Arrays:
The union of two sorted arrays is an operation that results in a new sorted array containing all the distinct elements from both arrays. The resulting array should not contain any duplicate elements. The union operation essentially merges the two arrays while maintaining the sorted order.
For example, let’s consider two sorted arrays:
Array A: [1, 3, 5, 7]
Array B: [2, 4, 6, 8]
The union of these arrays would be: [1, 2, 3, 4, 5, 6, 7, 8]
Intersection of Two Sorted Arrays:
The intersection of two sorted arrays is an operation that yields a new sorted array containing only the common elements between the two arrays. The resulting array will contain elements that are present in both arrays without any duplicates. The intersection operation identifies the shared values between the arrays.
For example, using the same two sorted arrays as above:
Array A: [1, 3, 5, 7]
Array B: [2, 4, 6, 7]
The intersection of these arrays would be: [7]
Dry Run For Union and Intersection of the Two Sorted Arrays in C
Let’s do a dry run of the code using the following arrays:
Array 1: [1, 3, 5, 7]
Array 2: [2, 4, 6, 7]
1. Initialization:
- The arrays arr1 and arr2 are defined with their respective elements.
- The variables size1 and size2 are set to the sizes of the arrays.
2. Printing the arrays:
- The printArray() function is called to print arr1 and arr2:
Output:
Array 1: 1 3 5 7
Array 2: 2 4 6 73. Finding the union:
- The findUnion() function is called with arr1, size1, arr2, and size2.
- The function initializes two pointers, i and j, to 0.
- The while loop is executed until both i and j are within their respective array bounds:
- In the first iteration, since arr1[i] (1) is less than arr2[j] (2), 1 is printed, and i is incremented.
- In the second iteration, arr1[i] (3) is greater than arr2[j] (2), so 2 is printed, and j is incremented.
- In the third iteration, arr1[i] (3) is equal to arr2[j] (3), so 3 is printed, and both i and j are incremented.
- In the fourth iteration, arr1[i] (5) is less than arr2[j] (6), so 5 is printed, and i is incremented.
- In the fifth iteration, arr1[i] (7) is equal to arr2[j] (7), so 7 is printed, and both i and j are incremented.
-
After the loop, the remaining elements in either array are printed.
Output:Union: 1 2 3 5 6 7
4. Finding the intersection:
- The findIntersection() function is called with arr1, size1, arr2, and size2.
- The function initializes two pointers, i and j, to 0.
- The while loop is executed until both i and j are within their respective array bounds:
- In the first iteration, arr1[i] (1) is less than arr2[j] (2), so i is incremented.
- In the second iteration, arr1[i] (3) is greater than arr2[j] (2), so j is incremented.
- In the third iteration, arr1[i] (3) is equal to arr2[j] (3), so 3 is printed, and both i and j are incremented.
- Since i has reached the end of arr1, the loop exits.
- The intersection between the two arrays is printed.
Output:
Intersection: 3Let’s see the code implementation of union and intersection of two sorted arrays in C.
Code Implementation
#include <stdio.h>
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void findUnion(int arr1[], int size1, int arr2[], int size2) {
int i = 0, j = 0;
while (i < size1 && j < size2) {
if (arr1[i] < arr2[j]) {
printf("%d ", arr1[i++]);
} else if (arr2[j] < arr1[i]) {
printf("%d ", arr2[j++]);
} else {
printf("%d ", arr1[i++]);
j++;
}
}
while (i < size1) {
printf("%d ", arr1[i++]);
}
while (j < size2) {
printf("%d ", arr2[j++]);
}
printf("\n");
}
void findIntersection(int arr1[], int size1, int arr2[], int size2) {
int i = 0, j = 0;
while (i < size1 && j < size2) {
if (arr1[i] < arr2[j]) {
i++;
} else if (arr2[j] < arr1[i]) {
j++;
} else {
printf("%d ", arr1[i++]);
j++;
}
}
printf("\n");
}
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 7};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
printf("Array 1: ");
printArray(arr1, size1);
printf("Array 2: ");
printArray(arr2, size2);
printf("Union: ");
findUnion(arr1, size1, arr2, size2);
printf("Intersection: ");
findIntersection(arr1, size1, arr2, size2);
return 0;
}
Output
Array 1: 1 3 5 7
Array 2: 2 4 6 7
Union: 1 2 3 4 5 6 7
Intersection: 7Explanation
In the above code, we have implemented two functions: findUnion() and findIntersection(). The findUnion() function takes two sorted arrays as input and prints their union. The findIntersection() function takes two sorted arrays as input and prints their intersection.
In the findUnion() function, we use two pointers i and j to traverse through the arrays. We compare the elements at these indices and print the smaller element. If the elements are equal, we print one of them and increment both pointers. After the traversal, we print any remaining elements in either array.
In the findIntersection() function, we again use two pointers i and j to traverse through the arrays. We compare the elements at these indices and print the common element if they are equal. If the elements are not equal, we increment the pointer corresponding to the smaller element. This way, we find the intersection between the two arrays.
Time Complexity
The union operation involves iterating through both arrays simultaneously and comparing the elements. In the worst-case scenario, where none of the elements in the arrays are equal, the code will perform a comparison for each element in both arrays exactly once. Therefore, the time complexity of the union operation is proportional to the total number of elements, which is O(n).
The intersection operation also involves iterating through both arrays simultaneously and comparing the elements. In the worst-case scenario, where there are no common elements between the arrays, the code will perform a comparison for each element in both arrays exactly once. Hence, the time complexity of the intersection operation is also proportional to the total number of elements, which is O(n).
Conclusion
In this article, we explored the concepts of union and intersection of two sorted arrays in the C programming language. We discussed the importance of these operations when working with arrays and demonstrated how to implement them efficiently.
We provided a code example that performs the union and intersection operations on two sorted arrays, leveraging the sorted nature of the arrays to optimize the algorithm. The code implementation ensures that the resulting arrays are sorted and contain distinct elements in the case of the union operation, or common elements in the case of the intersection operation.
Understanding the union and intersection operations is crucial in various scenarios, such as merging datasets, finding common elements, or eliminating duplicates from multiple arrays. By studying the provided code example and the explanation of the algorithm, readers should have gained a solid understanding of how to perform these operations effectively.
FAQs (Frequently Asked Questions):
Q1: Can the code handle arrays of different sizes?
Yes, the code implementation can handle arrays of different sizes. It takes into account the sizes of the input arrays as parameters to ensure correct iteration and comparison.
Q2: What happens if there are duplicate elements in the input arrays?
In the case of the union operation, the code implementation ensures that only distinct elements are included in the resulting array. It avoids printing duplicates by comparing elements and incrementing the pointers accordingly.
In the case of the intersection operation, the code identifies and prints only the common elements between the arrays, eliminating any duplicates.
Q3: Is it necessary for the input arrays to be sorted?
Yes, the code assumes that the input arrays are sorted in ascending order. The sorted nature of the arrays is crucial for the efficient implementation of the union and intersection operations. If the arrays are not sorted, the code may produce unexpected results.
Q4: Can the code handle arrays with negative numbers or zero?
Yes, the code implementation can handle arrays with negative numbers or zero. It treats all integers as valid elements and performs the necessary comparisons and operations accordingly.
Q5: Are there any limitations to the size of the arrays that can be used with this code?
The code itself does not have any specific limitations on the size of the arrays. However, the memory availability of the system may impose practical limitations on the maximum size of the arrays that can be processed.