CategoryC Program

C Program to find common elements between two arrays

Learn how to find distinct common elements between two C arrays while preserving order, with validated code, duplicate handling, and examples.

Tags#array#cprogram

An element is common to two arrays when the same value appears in both of them. In this article, each common value is included only once, even if it occurs multiple times in either array.

For example:

First array:  1 2 2 3 5 -1
Second array: 3 2 2 7 -1
Common values: 2 3 -1

The result follows the order of first appearance in the first array. The repeated value 2 is printed only once.

C Program to Find Common Elements Between Two Arrays

#include <stdio.h>

#define MAX_SIZE 100

int main(void) {
    int first[MAX_SIZE];
    int second[MAX_SIZE];
    int common[MAX_SIZE];
    int firstSize;
    int secondSize;
    int commonCount = 0;

    printf("Enter the number of elements in the first array: ");
    if (scanf("%d", &firstSize) != 1 ||
        firstSize < 1 || firstSize > MAX_SIZE) {
        printf("Please enter a size between 1 and %d.\n", MAX_SIZE);
        return 1;
    }

    printf("Enter %d elements for the first array:\n", firstSize);
    for (int index = 0; index < firstSize; index++) {
        if (scanf("%d", &first[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }
    }

    printf("Enter the number of elements in the second array: ");
    if (scanf("%d", &secondSize) != 1 ||
        secondSize < 1 || secondSize > MAX_SIZE) {
        printf("Please enter a size between 1 and %d.\n", MAX_SIZE);
        return 1;
    }

    printf("Enter %d elements for the second array:\n", secondSize);
    for (int index = 0; index < secondSize; index++) {
        if (scanf("%d", &second[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }
    }

    for (int firstIndex = 0; firstIndex < firstSize; firstIndex++) {
        int existsInSecond = 0;
        int alreadyAdded = 0;

        for (int secondIndex = 0;
             secondIndex < secondSize;
             secondIndex++) {
            if (first[firstIndex] == second[secondIndex]) {
                existsInSecond = 1;
                break;
            }
        }

        for (int commonIndex = 0;
             commonIndex < commonCount;
             commonIndex++) {
            if (first[firstIndex] == common[commonIndex]) {
                alreadyAdded = 1;
                break;
            }
        }

        if (existsInSecond && !alreadyAdded) {
            common[commonCount] = first[firstIndex];
            commonCount++;
        }
    }

    printf("Common elements: ");
    if (commonCount == 0) {
        printf("None");
    } else {
        for (int index = 0; index < commonCount; index++) {
            printf("%d ", common[index]);
        }
    }

    printf("\n");
    return 0;
}

Sample Output

Enter the number of elements in the first array: 6
Enter 6 elements for the first array:
1 2 2 3 5 -1
Enter the number of elements in the second array: 5
Enter 5 elements for the second array:
3 2 2 7 -1
Common elements: 2 3 -1

How the Program Works

For every element in the first array, the program performs three steps:

  1. Search the second array to determine whether the value appears there.
  2. Search the common array to determine whether the value has already been added.
  3. If the value exists in the second array and is not already in the result, append it to common.

Here is a dry run for the sample arrays:

Candidate from first arrayIn second array?Already added?Action
1NoNoSkip
2YesNoAdd 2
2YesYesSkip duplicate
3YesNoAdd 3
5NoNoSkip
-1YesNoAdd -1

The result is 2, 3, -1, in the order those values first occur in the first array.

Why Use a Separate common Array?

The result array serves two purposes:

  • It stores the common values so they can be printed together.
  • It prevents duplicate values from being added more than once.

The number of distinct common elements can never exceed the size of the smaller input array, so an array with MAX_SIZE positions is sufficient under the program's input limits.

Set Intersection Versus Multiset Intersection

This program treats both inputs like sets and prints each shared value once. This is called a distinct intersection.

A multiset intersection preserves duplicate counts. For example:

First array:  2 2 2 5
Second array: 2 2 7
Distinct intersection: 2
Multiset intersection: 2 2

The multiset result contains 2 twice because the value occurs at least twice in both arrays. The program in this article intentionally produces the distinct intersection.

What If There Are No Common Elements?

If no value appears in both arrays, commonCount remains 0:

First array:  1 3 5
Second array: 2 4 6
Common elements: None

Does It Work with Negative Numbers and Zero?

Yes. The algorithm uses direct integer equality, so negative values and zero need no special handling:

First array:  -2 0 5 8
Second array: 7 0 -2
Common elements: -2 0

Does Array Order Matter?

The membership result does not depend on order, but the order of the printed values does. Because the outer loop traverses the first array, the result follows the first array's order.

Swapping the two input arrays can therefore change the output order without changing which distinct values are common.

Alternative Approaches

  • Sort and use two pointers: After sorting both arrays, two indices can find common values efficiently. The total cost is typically O(n log n + m log m), and sorting changes the arrays unless copies are used.
  • Frequency table: Works in linear time when values lie in a small, known range, but range limits and negative values require care.
  • Hash set: Provides expected O(n + m) time for arbitrary values, but standard C has no built-in hash-set type.

The nested-loop method is simple, accepts every int, and preserves the original arrays.

Time and Space Complexity

If the first array has n elements, the second has m, and the result contains k distinct values:

  • Time complexity: O(n × m + n × k), because each first-array value may scan the second array and the current result. For similarly sized arrays, the worst case is O(n²).
  • Extra space complexity: O(k) for the distinct common elements, with k ≤ min(n, m).

Common Mistakes

  • Printing a shared value once for every matching pair and producing duplicates.
  • Comparing only elements at the same index in the two arrays.
  • Forgetting to reset existsInSecond and alreadyAdded for each candidate.
  • Assuming both arrays have the same length.
  • Sorting the original arrays when their order must be preserved.
  • Confusing distinct intersection with multiset intersection.

By checking membership in the second array and preventing repeated additions, the program finds every distinct common element while preserving its first-array order.