Last Updated on August 12, 2024 by Abhishek Sharma
Handling arrays is a fundamental aspect of programming in C, and operations like finding the union and intersection of two sorted arrays are common tasks that require both logical thinking and a good understanding of algorithms. The union of two arrays combines the elements of both arrays, removing duplicates, while the intersection finds the common elements between the two. Since the arrays are already sorted, we can leverage this property to efficiently compute both the union and the intersection. This article will guide you through the process of performing these operations on two sorted arrays in C, highlighting the algorithms used and offering practical examples.
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
The union and intersection of two sorted arrays in C can be computed efficiently by taking advantage of their sorted nature. By iterating through both arrays simultaneously, you can reduce the time complexity of these operations compared to unsorted arrays. Understanding these concepts is essential for solving many real-world problems involving arrays, where efficient data handling can significantly improve performance. Mastering these techniques will enhance your ability to manipulate data structures in C and optimize your programs for better efficiency.
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) related to Union and Intersection of the Two Sorted Arrays in C
Here are some FAQs related to Union and Intersection of the Two Sorted Arrays in C:
1. What is the union of two sorted arrays?
The union of two sorted arrays is a combined array that contains all the unique elements from both arrays, sorted in ascending order. Duplicate elements are included only once.
2. How do I find the intersection of two sorted arrays in C?
To find the intersection of two sorted arrays in C, you can iterate through both arrays simultaneously, comparing elements and storing the common ones in a new array.
3. Can the union and intersection of two sorted arrays be done in linear time?
Yes, since the arrays are sorted, both the union and intersection operations can be performed in linear time, O(n + m), where n and m are the lengths of the two arrays.
4. What should I consider when implementing union and intersection functions in C?
When implementing these functions, consider edge cases such as empty arrays, arrays with no common elements, and arrays with all elements in common. Also, ensure that your functions handle duplicates correctly.
5. Is it necessary for the arrays to be sorted to find their union and intersection?
While it’s not strictly necessary for arrays to be sorted to find their union and intersection, sorting the arrays beforehand allows for more efficient algorithms with lower time complexity.