The intersection of two arrays is a new array that contains all elements present in both arrays. This operation is a fundamental concept in programming, used in data processing, set operations, and algorithm problems. Understanding how to find the intersection helps in comparing datasets and extracting common elements efficiently.
In this tutorial, we will explore multiple ways to find the intersection of two arrays in C. Each approach includes full executable code examples with detailed explanations. By the end of this guide, you will understand how to identify common elements, manage duplicates, and write efficient programs for intersection operations.
Understanding the Problem
The intersection of two arrays A and B is a new array that contains only the elements that exist in both A and B. For example, if:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}Then the intersection will be:
Intersection = {3, 4}The challenge is to efficiently find elements common to both arrays without unnecessary duplication or repeated comparisons. We will cover different approaches from basic nested loops to hashing for large arrays.
Program 1: Using Nested Loops
The simplest way to find the intersection is to use nested loops. We compare each element of the first array with all elements of the second array and add it to the result only if it is present in both.
#include <stdio.h>
int main() {
int A[] = {1, 2, 3, 4};
int B[] = {3, 4, 5, 6};
int sizeA = sizeof(A)/sizeof(A[0]);
int sizeB = sizeof(B)/sizeof(B[0]);
int result[sizeA < sizeB ? sizeA : sizeB];
int sizeR = 0;
for(int i = 0; i < sizeA; i++) {
for(int j = 0; j < sizeB; j++) {
if(A[i] == B[j]) {
int exists = 0;
for(int k = 0; k < sizeR; k++) {
if(result[k] == A[i]) {
exists = 1;
break;
}
}
if(!exists) {
result[sizeR++] = A[i];
}
}
}
}
printf("Intersection of two arrays: ");
for(int i = 0; i < sizeR; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}In this approach, we check each element of A against all elements of B. To avoid duplicates, we also check if the element is already added to the result array. While simple, this method can be slow for large arrays due to repeated comparisons.
Program 2: Using Sorting and Two Pointers
A more efficient method is to sort both arrays and use a two-pointer technique to find common elements.
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int A[] = {1, 2, 3, 4};
int B[] = {3, 4, 5, 6};
int sizeA = sizeof(A)/sizeof(A[0]);
int sizeB = sizeof(B)/sizeof(B[0]);
int result[sizeA < sizeB ? sizeA : sizeB], sizeR = 0;
qsort(A, sizeA, sizeof(int), compare);
qsort(B, sizeB, sizeof(int), compare);
int i = 0, j = 0;
while(i < sizeA && j < sizeB) {
if(A[i] < B[j]) i++;
else if(B[j] < A[i]) j++;
else {
result[sizeR++] = A[i];
i++; j++;
}
}
printf("Intersection of two arrays: ");
for(int k = 0; k < sizeR; k++) {
printf("%d ", result[k]);
}
printf("\n");
return 0;
}Here, we first sort both arrays using qsort(). Then, we traverse both arrays simultaneously, adding elements to the result only when they are equal. This method is much faster for larger arrays compared to nested loops.
Program 3: Using Hashing
For large arrays or when performance is critical, we can use a hash table to track elements of one array and check if elements of the second array exist in it.
#include <stdio.h>
#include <stdbool.h>
#define MAX 100 // assuming all numbers are <= 100
int main() {
int A[] = {1, 2, 3, 4};
int B[] = {3, 4, 5, 6};
int sizeA = sizeof(A) / sizeof(A[0]);
int sizeB = sizeof(B) / sizeof(B[0]);
bool hash[MAX+1] = {false};
int result[sizeA < sizeB ? sizeA : sizeB]; // intersection size <= smaller array
int sizeR = 0;
for(int i = 0; i < sizeA; i++) {
hash[A[i]] = true;
}
for(int i = 0; i < sizeB; i++) {
if(hash[B[i]]) {
result[sizeR++] = B[i];
hash[B[i]] = false; // avoid duplicates
}
}
printf("Intersection of two arrays: ");
for(int i = 0; i < sizeR; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}This approach uses extra memory but is very fast. It works efficiently when array values are within a known range and eliminates duplicates in the intersection.
Performance Comparison
| Method | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Nested Loops | O(n*m) | O(min(n,m)) | Simple, but inefficient for large arrays. |
| Sorting + Two Pointers | O(n log n + m log m) | O(min(n,m)) | Fast and efficient; changes the original order due to sorting. |
| Hashing | O(n + m) | O(k) | Very fast for large arrays; uses extra memory for hash table. |
Which Method Should You Use?
The nested loop method is easiest to understand and suitable for small arrays or beginner practice.
The sorting and two-pointer method is better for medium-sized arrays and when sorted results are acceptable.
The hashing method is ideal for large arrays and performance-critical applications. It is very fast but requires extra memory.
In practice, hashing is commonly used for large datasets, while nested loops or sorting can work for smaller datasets or learning exercises.
FAQs
Q1: Can this handle arrays with negative numbers?
Yes, nested loops and sorting work with negative numbers. Hashing needs adjustments if using array indices for the hash table.
Q2: Does this method preserve order?
Nested loops preserve the order of the first array, sorting changes the order, and hashing may not preserve the original order unless handled carefully.
Q3: Can I use memcpy() to simplify copying elements?
Yes, memcpy() can copy elements, but you still need to check for duplicates when finding the intersection.
Conclusion
Finding the intersection of two arrays is a fundamental operation in C programming. We explored nested loops, sorting with two pointers, and hashing methods. Beginners can start with nested loops for clarity, while hashing is optimal for large datasets and performance-critical tasks. Mastering these techniques strengthens your array manipulation and problem-solving skills in C.
References & Additional Resources
A curated collection of textbooks and tutorials for learning arrays, array operations, and hashing techniques in C.
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language, 2nd Edition, Prentice Hall, 1988 – The foundational text covering arrays, pointers, functions, and core C programming concepts.
- GeeksforGeeks: C Arrays – Introduction to arrays in C, including declaration, initialization, traversal, and basic operations.
- GeeksforGeeks: Intersection of Two Arrays – Demonstrates how to find the intersection of two arrays with C programming examples.
- GeeksforGeeks: Hashing in Data Structure – Explains the concept of hashing, hash tables, and their applications for efficient data storage and retrieval.
