Finding Arrays Are Disjoint Or Not In C Program

Disjoint arrays are two or more arrays that do not share any common elements. Understanding how to identify if arrays are disjoint is fundamental in various programming challenges and data management tasks.

In this article, you will learn different approaches to determine if two arrays are disjoint using C programming.

Problem Statement

The problem is to ascertain whether two given arrays, say arr1 and arr2, contain any identical elements. If they do not share any common elements, they are considered disjoint; otherwise, they are not. This check is crucial for maintaining data integrity or optimizing algorithms where overlapping data could lead to incorrect results or inefficiencies.

Example

Consider two arrays: arr1 = {1, 2, 3, 4} arr2 = {5, 6, 7} These arrays are disjoint because no element from arr1 is present in arr2, and vice-versa.

However, if: arr1 = {1, 2, 3, 4} arr2 = {4, 5, 6} These arrays are not disjoint because the element 4 is common to both arrays.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following C concepts is helpful:

• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iterating through arrays.
• Conditional Statements: if statements for comparisons.
• Functions: Defining and calling functions.
• Pointers (optional but useful for sorting): Basic understanding of memory addresses.

 

For the sorting approach, knowledge of a sorting algorithm like qsort or implementing a simple sort (e.g., bubble sort, selection sort) is beneficial.

Use Cases or Case Studies

Determining if arrays are disjoint has several practical applications:

• Database Management: Ensuring that primary keys in different tables (or data sets) don't overlap when they shouldn't.
• Resource Allocation: Checking if a new set of resource requests conflicts with currently allocated resources.
• Algorithm Optimization: In graph theory or set operations, identifying disjoint sets can simplify algorithms or prevent redundant computations.
• Collision Detection: In simple simulations or games, checking if two lists of object coordinates (representing their bounds) intersect.
• Data Validation: Verifying that input data sets are unique when uniqueness is a requirement.

 

Solution Approaches

We will explore three common approaches to determine if two arrays are disjoint.

1. Brute-Force Comparison (Naive Approach)

This is the most straightforward method. It involves comparing every element of the first array with every element of the second array.

• Summary: Use nested loops to compare each element from arr1 with every element from arr2.
• Code Example:

 

// Disjoint Arrays - Brute-Force
#include <stdio.h>
#include <stdbool.h> // For boolean type

// Function to check if two arrays are disjoint using brute-force
bool areArraysDisjoint_BruteForce(int arr1[], int n1, int arr2[], int n2) {
    // Step 1: Iterate through each element of the first array
    for (int i = 0; i < n1; i++) {
        // Step 2: Iterate through each element of the second array
        for (int j = 0; j < n2; j++) {
            // Step 3: If a common element is found, arrays are not disjoint
            if (arr1[i] == arr2[j]) {
                return false; // Found a common element
            }
        }
    }
    // Step 4: If no common elements were found after all comparisons
    return true; // Arrays are disjoint
}

int main() {
    int arr1_a[] = {1, 2, 3, 4};
    int n1_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {5, 6, 7};
    int n2_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    printf("Arrays 1A and 2A: ");
    if (areArraysDisjoint_BruteForce(arr1_a, n1_a, arr2_a, n2_a)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    int arr1_b[] = {10, 20, 30};
    int n1_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {20, 40, 50};
    int n2_b = sizeof(arr2_b) / sizeof(arr2_b[0]);

    printf("Arrays 1B and 2B: ");
    if (areArraysDisjoint_BruteForce(arr1_b, n1_b, arr2_b, n2_b)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    return 0;
}

Run

• Sample Output:

Arrays 1A and 2A: Disjoint
Arrays 1B and 2B: Not Disjoint

 

• Stepwise Explanation:

1. The areArraysDisjointBruteForce function takes two integer arrays and their sizes as input.
2. It uses an outer for loop to iterate through each element of the first array (arr1).
3. Inside, an inner for loop iterates through each element of the second array (arr2).
4. An if condition checks if the current element from arr1 is equal to the current element from arr2.
5. If a match is found, it immediately returns false because the arrays are not disjoint.
6. If the loops complete without finding any common elements, it means the arrays are disjoint, and the function returns true.

2. Sorting and Two-Pointer Approach

This approach improves efficiency by first sorting one or both arrays. Once sorted, we can use a two-pointer technique to find common elements much faster.

• Summary: Sort one array (or both), then use two pointers to traverse them simultaneously, checking for common elements.
• Code Example:

 

// Disjoint Arrays - Sorting and Two Pointers
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <stdbool.h>

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// Function to check if two arrays are disjoint using sorting and two pointers
bool areArraysDisjoint_SortAndPointers(int arr1[], int n1, int arr2[], int n2) {
    // Step 1: Sort both arrays
    qsort(arr1, n1, sizeof(int), compare);
    qsort(arr2, n2, sizeof(int), compare);

    // Step 2: Initialize two pointers for sorted arrays
    int i = 0; // Pointer for arr1
    int j = 0; // Pointer for arr2

    // Step 3: Traverse both arrays with two pointers
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            i++; // Move pointer of arr1 if its element is smaller
        } else if (arr2[j] < arr1[i]) {
            j++; // Move pointer of arr2 if its element is smaller
        } else {
            return false; // Elements are equal, arrays are not disjoint
        }
    }
    // Step 4: If loop completes without finding common elements
    return true; // Arrays are disjoint
}

int main() {
    int arr1_a[] = {1, 2, 3, 4};
    int n1_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {5, 6, 7};
    int n2_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    printf("Arrays 1A and 2A (after sort): ");
    if (areArraysDisjoint_SortAndPointers(arr1_a, n1_a, arr2_a, n2_a)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    int arr1_b[] = {10, 20, 30};
    int n1_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {20, 40, 50};
    int n2_b = sizeof(arr2_b) / sizeof(arr2_b[0]);

    printf("Arrays 1B and 2B (after sort): ");
    if (areArraysDisjoint_SortAndPointers(arr1_b, n1_b, arr2_b, n2_b)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    return 0;
}

Run

• Sample Output:

Arrays 1A and 2A (after sort): Disjoint
Arrays 1B and 2B (after sort): Not Disjoint

 

• Stepwise Explanation:

1. A compare function is defined for qsort to sort integers in ascending order.
2. The areArraysDisjointSortAndPointers function first sorts both arr1 and arr2 using qsort. This is a crucial step for the two-pointer approach.
3. Two pointers, i and j, are initialized to 0 to point to the beginning of arr1 and arr2, respectively.
4. A while loop continues as long as both pointers are within their respective array bounds.
5. Inside the loop:
   • If arr1[i] is less than arr2[j], it means arr1[i] cannot be in arr2 (since arr2 is sorted), so we increment i.

• If arr2[j] is less than arr1[i], it means arr2[j] cannot be in arr1, so we increment j.
• If arr1[i] is equal to arr2[j], a common element is found, and the function returns false.

1. If the loop finishes without finding any common elements, it means the arrays are disjoint, and the function returns true.

3. Using a Frequency Array (Hash Set Simulation)

This method uses an auxiliary boolean array (or frequency array) to keep track of elements seen in the first array. It's efficient if the range of numbers in the arrays is small and positive.

• Summary: Create a boolean array (acting as a hash set) to mark elements present in arr1. Then, iterate through arr2 and check if any element is marked in the boolean array.
• Code Example:
• Assumption: Elements are non-negative and within a reasonable range (e.g., 0 to MAXVAL - 1).

 

// Disjoint Arrays - Frequency Array
#include <stdio.h>
#include <stdbool.h>
#include <string.h> // For memset

#define MAX_VAL 1001 // Assuming array elements are between 0 and 1000

// Function to check if two arrays are disjoint using a frequency array
bool areArraysDisjoint_FrequencyArray(int arr1[], int n1, int arr2[], int n2) {
    // Step 1: Create a boolean frequency array and initialize to false
    // 'seen[x]' will be true if 'x' is present in arr1
    bool seen[MAX_VAL];
    memset(seen, false, sizeof(seen)); // Initialize all to false

    // Step 2: Populate the 'seen' array with elements from arr1
    for (int i = 0; i < n1; i++) {
        // Check if element is within assumed range
        if (arr1[i] >= 0 && arr1[i] < MAX_VAL) {
            seen[arr1[i]] = true;
        } else {
            // Handle elements out of range or return false if necessary
            // For simplicity, we'll ignore out-of-range elements for this example,
            // but in a real scenario, you'd handle this.
        }
    }

    // Step 3: Iterate through arr2 and check against the 'seen' array
    for (int i = 0; i < n2; i++) {
        // Check if element is within assumed range and was seen in arr1
        if (arr2[i] >= 0 && arr2[i] < MAX_VAL && seen[arr2[i]]) {
            return false; // Found a common element
        }
        // If element is out of range, this approach might miss commonalities
        // if the corresponding element in arr1 was also out of range.
        // For production, ensure MAX_VAL covers all possible values.
    }
    // Step 4: If no common elements were found
    return true; // Arrays are disjoint
}

int main() {
    int arr1_a[] = {1, 2, 3, 4};
    int n1_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {5, 6, 7};
    int n2_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    printf("Arrays 1A and 2A (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_a, n1_a, arr2_a, n2_a)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    int arr1_b[] = {10, 20, 30};
    int n1_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {20, 40, 50};
    int n2_b = sizeof(arr2_b) / sizeof(arr2_b[0]);

    printf("Arrays 1B and 2B (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_b, n1_b, arr2_b, n2_b)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    int arr1_c[] = {990, 10, 500};
    int n1_c = sizeof(arr1_c) / sizeof(arr1_c[0]);
    int arr2_c[] = {10, 20, 30};
    int n2_c = sizeof(arr2_c) / sizeof(arr2_c[0]);

    printf("Arrays 1C and 2C (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_c, n1_c, arr2_c, n2_c)) {
        printf("Disjoint\\n");
    } else {
        printf("Not Disjoint\\n");
    }

    return 0;
}

Run

• Sample Output:

Arrays 1A and 2A (freq array): Disjoint
Arrays 1B and 2B (freq array): Not Disjoint
Arrays 1C and 2C (freq array): Not Disjoint

 

• Stepwise Explanation:

1. A boolean array seen of size MAXVAL is declared and initialized to false using memset. MAX_VAL should be chosen to be greater than the maximum possible value in the arrays.
2. The first loop iterates through arr1. For each element arr1[i], if it's within the valid range, seen[arr1[i]] is set to true. This marks its presence.
3. The second loop iterates through arr2. For each element arr2[i], it checks if seen[arr2[i]] is true.
4. If seen[arr2[i]] is true, it means arr2[i] was found in arr1, so the arrays are not disjoint, and the function returns false.
5. If the second loop completes without finding any marked elements, the arrays are disjoint, and the function returns true.

Conclusion

Determining if two arrays are disjoint is a common task in programming, with various approaches offering different trade-offs in terms of time and space complexity. The brute-force method is simple but less efficient for large arrays. The sorting and two-pointer approach offers a good balance of efficiency and practicality for most cases. The frequency array method provides the fastest average-case performance if the range of elements is constrained, making it suitable for specific scenarios like counting elements or checking for small integer ranges. Choosing the right method depends on the array sizes, element range, and performance requirements.

Summary

• Disjoint arrays share no common elements.
• Brute-Force:
• Compares every element of one array with every element of the other.
• Time Complexity: O(N\*M), where N and M are array sizes.
• Space Complexity: O(1).
• Sorting and Two Pointers:
• Sorts both arrays first, then uses two pointers for efficient comparison.
• Time Complexity: O(N log N + M log M) for sorting, O(N + M) for comparison, total O(N log N + M log M).
• Space Complexity: O(1) or O(log N) for qsort depending on implementation.
• Frequency Array (Hash Set Simulation):
• Uses a boolean array to mark elements seen in the first array, then checks the second.
• Assumes a limited, positive range for array elements.
• Time Complexity: O(N + M + Range), where Range is the maximum possible element value.
• Space Complexity: O(Range) for the frequency array.
• The choice of approach depends on data characteristics and performance needs.