Intersection of Two Arrays in C: Program to Find Common Elements

📚 In this tutorial, you will learn:

What is intersection of two arrays
How to find common elements between two arrays
How to handle duplicates in intersection
Step-by-step explanation of the program
Practice exercises to test your understanding

Introduction

In this tutorial, we will learn how to write a C program to find the intersection of two arrays.

The intersection of two arrays is a set of elements that are common to both arrays. It is used in many real-world applications, such as:

Finding common friends between two users on social media
Finding common products in two shopping lists
Finding common keywords in two documents
Finding common elements in two datasets

💡 Key Point: The intersection of two arrays contains only the elements that appear in both arrays. Duplicates are typically handled by keeping only one occurrence.

C Program for Intersection of Two Arrays

#include <stdio.h>

int main() {
    int n1, n2, i, j, k;
    int count = 0;
    
    // ====== FIRST ARRAY ======
    printf("Enter the number of elements in first array: ");
    scanf("%d", &n1);
    int arr1[n1];
    
    printf("Enter %d elements:\n", n1);
    for(i = 0; i < n1; i++) {
        scanf("%d", &arr1[i]);
    }
    
    // ====== SECOND ARRAY ======
    printf("\nEnter the number of elements in second array: ");
    scanf("%d", &n2);
    int arr2[n2];
    
    printf("Enter %d elements:\n", n2);
    for(i = 0; i < n2; i++) {
        scanf("%d", &arr2[i]);
    }
    
    // ====== FIND INTERSECTION ======
    // Maximum possible size of intersection is the smaller array
    int intersection[n1 < n2 ? n1 : n2];
    
    for(i = 0; i < n1; i++) {
        for(j = 0; j < n2; j++) {
            if(arr1[i] == arr2[j]) {
                // Check if element already added to intersection
                int duplicate = 0;
                for(k = 0; k < count; k++) {
                    if(intersection[k] == arr1[i]) {
                        duplicate = 1;
                        break;
                    }
                }
                if(duplicate == 0) {
                    intersection[count] = arr1[i];
                    count++;
                }
                break;  // Found match, no need to continue inner loop
            }
        }
    }
    
    // ====== DISPLAY ======
    printf("\nFirst array: ");
    for(i = 0; i < n1; i++) {
        printf("%d ", arr1[i]);
    }
    
    printf("\nSecond array: ");
    for(i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    
    printf("\n\nIntersection of two arrays: ");
    if(count == 0) {
        printf("No common elements found.");
    } else {
        for(i = 0; i < count; i++) {
            printf("%d ", intersection[i]);
        }
    }
    printf("\n");
    
    return 0;
}

Sample Output

Enter the number of elements in first array: 5
Enter 5 elements:
10 20 30 40 50

Enter the number of elements in second array: 4
Enter 4 elements:
30 50 60 70

First array: 10 20 30 40 50
Second array: 30 50 60 70

Intersection of two arrays: 30 50

Example with No Common Elements:

Enter the number of elements in first array: 4
Enter 4 elements:
10 20 30 40

Enter the number of elements in second array: 3
Enter 3 elements:
50 60 70

First array: 10 20 30 40
Second array: 50 60 70

Intersection of two arrays: No common elements found.

Example with Duplicates:

Enter the number of elements in first array: 6
Enter 6 elements:
10 20 10 30 20 40

Enter the number of elements in second array: 5
Enter 5 elements:
10 10 20 50 60

First array: 10 20 10 30 20 40
Second array: 10 10 20 50 60

Intersection of two arrays: 10 20

Program Explanation

Let's break down the code step by step:

Include Header File: #include <stdio.h> includes the standard input/output library.
Declare Variables:
- int n1, n2; — sizes of the two arrays
- int i, j, k; — loop counters
- int count = 0; — number of elements in the intersection
Read Arrays: Reads the size and elements of both arrays.
Find Intersection:
- The outer loop iterates through each element of arr1
- The inner loop checks if the element exists in arr2
- If found, check if it's already in the intersection (to avoid duplicates)
- If not a duplicate, add it to the intersection array
- break out of the inner loop after finding a match
Display Results: Prints both arrays and the intersection.
Return: return 0; indicates successful program execution.

📝 Note: The size of the intersection array is set to the size of the smaller array, as the intersection cannot be larger than the smaller array.

Algorithm to Find Intersection of Two Arrays

Step-by-step algorithm:

Start
Read the elements of first array (arr1)
Read the elements of second array (arr2)
Create an empty intersection array
For i = 0 to n1-1:
- For j = 0 to n2-1:
  - If arr1[i] == arr2[j]:
    - Check if arr1[i] is already in intersection
    - If not present, add it to intersection
    - Break from inner loop
Print the intersection array
End

Intersection of Sorted Arrays (More Efficient)

If both arrays are sorted, we can find the intersection in O(n1 + n2) time using a two-pointer approach.

#include <stdio.h>

int main() {
    int n1, n2, i, j, k;
    int count = 0;
    
    printf("Enter the number of elements in first sorted array: ");
    scanf("%d", &n1);
    int arr1[n1];
    printf("Enter %d sorted elements:\n", n1);
    for(i = 0; i < n1; i++) {
        scanf("%d", &arr1[i]);
    }
    
    printf("\nEnter the number of elements in second sorted array: ");
    scanf("%d", &n2);
    int arr2[n2];
    printf("Enter %d sorted elements:\n", n2);
    for(i = 0; i < n2; i++) {
        scanf("%d", &arr2[i]);
    }
    
    // Find intersection using two-pointer technique
    int intersection[n1 < n2 ? n1 : n2];
    i = 0;
    j = 0;
    
    while(i < n1 && j < n2) {
        if(arr1[i] < arr2[j]) {
            i++;
        }
        else if(arr1[i] > arr2[j]) {
            j++;
        }
        else {
            // Equal elements found
            // Check for duplicates in intersection
            int duplicate = 0;
            for(k = 0; k < count; k++) {
                if(intersection[k] == arr1[i]) {
                    duplicate = 1;
                    break;
                }
            }
            if(duplicate == 0) {
                intersection[count] = arr1[i];
                count++;
            }
            i++;
            j++;
        }
    }
    
    // Display results
    printf("\nFirst array: ");
    for(i = 0; i < n1; i++) {
        printf("%d ", arr1[i]);
    }
    
    printf("\nSecond array: ");
    for(i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    
    printf("\n\nIntersection of two arrays: ");
    if(count == 0) {
        printf("No common elements found.");
    } else {
        for(i = 0; i < count; i++) {
            printf("%d ", intersection[i]);
        }
    }
    printf("\n");
    
    return 0;
}

Sample Output:

Enter the number of elements in first sorted array: 6
Enter 6 sorted elements:
10 20 30 40 50 60

Enter the number of elements in second sorted array: 4
Enter 4 sorted elements:
30 40 60 70

First array: 10 20 30 40 50 60
Second array: 30 40 60 70

Intersection of two arrays: 30 40 60

How Two-Pointer Intersection Works

Two Pointers: i points to arr1, j points to arr2
Compare: If arr1[i] < arr2[j], move i forward
If arr1[i] > arr2[j], move j forward
If arr1[i] == arr2[j], it's a common element
Add to intersection and move both pointers
Time Complexity: O(n1 + n2)

Time and Space Complexity

Method	Time Complexity	Space Complexity
Nested Loop (Unsorted)	O(n1 × n2)	O(min(n1, n2))
Two-Pointer (Sorted)	O(n1 + n2)	O(min(n1, n2))

💻 Practice Exercise

Challenge 1: Modify the program to find the intersection of three arrays.

Challenge 2: Find the intersection of two arrays without using extra space (modify one of the arrays).

🔍 Click to Show Solution for Challenge 2

#include <stdio.h>

int main() {
    int n1, n2, i, j, k;
    
    printf("Enter the number of elements in first array: ");
    scanf("%d", &n1);
    int arr1[n1];
    printf("Enter %d elements:\n", n1);
    for(i = 0; i < n1; i++) {
        scanf("%d", &arr1[i]);
    }
    
    printf("Enter the number of elements in second array: ");
    scanf("%d", &n2);
    int arr2[n2];
    printf("Enter %d elements:\n", n2);
    for(i = 0; i < n2; i++) {
        scanf("%d", &arr2[i]);
    }
    
    // Find intersection without extra space
    int count = 0;
    for(i = 0; i < n1; i++) {
        for(j = 0; j < n2; j++) {
            if(arr1[i] == arr2[j]) {
                // Check if already in arr1 (first part)
                int duplicate = 0;
                for(k = 0; k < count; k++) {
                    if(arr1[k] == arr1[i]) {
                        duplicate = 1;
                        break;
                    }
                }
                if(duplicate == 0) {
                    // Store intersection in the beginning of arr1
                    arr1[count] = arr1[i];
                    count++;
                }
                break;
            }
        }
    }
    
    printf("\nIntersection of two arrays: ");
    if(count == 0) {
        printf("No common elements found.");
    } else {
        for(i = 0; i < count; i++) {
            printf("%d ", arr1[i]);
        }
    }
    printf("\n");
    
    return 0;
}

Frequently Asked Questions

1. What is the intersection of two arrays?

The intersection of two arrays is a set of elements that appear in both arrays. It contains only the common elements.

2. How do you find the intersection of two arrays in C?

You can use nested loops to compare each element of the first array with each element of the second array. If a match is found and it's not already in the result, add it to the intersection.

3. What is the difference between intersection and union?

Intersection contains elements common to both arrays. Union contains all unique elements from both arrays combined.

4. How do you handle duplicates in intersection?

Before adding an element to the intersection, check if it's already present. This ensures each element appears only once in the result.

5. Can I find intersection without using extra space?

Yes, you can store the intersection in one of the original arrays by overwriting elements at the beginning of the array.

💡 Tip: If both arrays are sorted, use the two-pointer approach for a more efficient O(n1 + n2) solution.

Previous Topic: -->> Remove Duplicate Elements from Array || Next topic: -->> Union of Two Arrays

📚 Explore More Topics