Finding Arrays Are Disjoint Or Not In Java Program

Determining if two arrays are disjoint is a common task in programming, crucial for ensuring data integrity or preventing conflicts in various applications. Disjoint arrays are those that share no common elements.

In this article, you will learn how to identify if two arrays are disjoint using different approaches in Java, comparing their efficiency and practical applicability.

Problem Statement

The core problem is to efficiently check if two given arrays, say arr1 and arr2, have any elements in common. If even one element exists in both arrays, they are not disjoint. If no such element exists, they are considered disjoint. This check is vital when you need to confirm that two sets of data are completely independent of each other.

For instance, consider managing unique IDs for users and administrators. If any ID appears in both lists, it indicates a critical overlap that needs to be resolved.

Example

Let's look at examples of disjoint and non-disjoint arrays.

Disjoint Arrays Example: arr1 = {1, 2, 3} arr2 = {4, 5, 6} Result: true (They share no common elements)

Non-Disjoint Arrays Example: arr1 = {1, 2, 3} arr2 = {3, 4, 5} Result: false (They share the element 3)

Background & Knowledge Prerequisites

To understand the solutions presented, familiarity with the following Java concepts is beneficial:

• Arrays: Basic declaration, initialization, and iteration.
• Loops: for loops for iterating through array elements.
• Collections Framework: Specifically, the HashSet class for efficient storage and lookup of elements.
• Conditional Statements: if-else for logic control.

For setting up, no special imports beyond java.util.* are typically needed for HashSet and Arrays utility classes.

Use Cases or Case Studies

Checking for disjoint arrays has several practical applications:

• Resource Allocation: Ensuring that two different processes or users are not assigned the same resource IDs (e.g., port numbers, memory blocks).
• Data Validation: Verifying that two input lists of unique identifiers (e.g., product SKUs, employee IDs) do not contain duplicates when combined or compared.
• Scheduling: Confirming that two event schedules (represented by time slots or resource IDs) do not overlap, indicating a conflict.
• Security Permissions: Ensuring that a user account does not simultaneously hold conflicting permissions represented by sets of access codes.
• Database Operations: Before merging or joining data from two tables, checking for disjoint primary keys to prevent data integrity issues.

Solution Approaches

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

Approach 1: Brute-Force with Nested Loops

Summary: This method involves comparing every element of the first array with every element of the second array. If a match is found, the arrays are not disjoint.

// DisjointArrayBruteForce
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    /**
     * Checks if two integer arrays are disjoint using a brute-force approach.
     * @param arr1 The first array.
     * @param arr2 The second array.
     * @return true if the arrays are disjoint (no common elements), false otherwise.
     */
    public static boolean areArraysDisjointBruteForce(int[] arr1, int[] arr2) {
        // Step 1: Iterate through each element of the first array.
        for (int i = 0; i < arr1.length; i++) {
            // Step 2: For each element in arr1, iterate through all elements of the second array.
            for (int j = 0; j < arr2.length; j++) {
                // Step 3: Compare the current elements.
                if (arr1[i] == arr2[j]) {
                    // Step 4: If a common element is found, the arrays are not disjoint.
                    return false;
                }
            }
        }
        // Step 5: If no common elements are found after all comparisons, the arrays are disjoint.
        return true;
    }

    public static void main(String[] args) {
        // Test Case 1: Disjoint arrays
        int[] arr1_case1 = {1, 2, 3};
        int[] arr2_case1 = {4, 5, 6};
        System.out.println("Arrays: {1, 2, 3} and {4, 5, 6}");
        System.out.println("Are disjoint (Brute-Force)? " + areArraysDisjointBruteForce(arr1_case1, arr2_case1)); // Expected: true

        // Test Case 2: Non-disjoint arrays
        int[] arr1_case2 = {1, 2, 3};
        int[] arr2_case2 = {3, 4, 5};
        System.out.println("\\nArrays: {1, 2, 3} and {3, 4, 5}");
        System.out.println("Are disjoint (Brute-Force)? " + areArraysDisjointBruteForce(arr1_case2, arr2_case2)); // Expected: false

        // Test Case 3: Empty arrays
        int[] arr1_case3 = {};
        int[] arr2_case3 = {1, 2, 3};
        System.out.println("\\nArrays: {} and {1, 2, 3}");
        System.out.println("Are disjoint (Brute-Force)? " + areArraysDisjointBruteForce(arr1_case3, arr2_case3)); // Expected: true
    }
}

Run

Sample Output:

Arrays: {1, 2, 3} and {4, 5, 6}
Are disjoint (Brute-Force)? true

Arrays: {1, 2, 3} and {3, 4, 5}
Are disjoint (Brute-Force)? false

Arrays: {} and {1, 2, 3}
Are disjoint (Brute-Force)? true

Stepwise Explanation:

1. A method areArraysDisjointBruteForce takes two integer arrays as input.
2. The outer for loop iterates from the first element to the last element of arr1.
3. The inner for loop iterates from the first element to the last element of arr2 for each element of arr1.
4. Inside the inner loop, elements arr1[i] and arr2[j] are compared.
5. If arr1[i] == arr2[j] is true, it means a common element is found, so the method immediately returns false.
6. If the loops complete without finding any common elements, it means the arrays are disjoint, and the method returns true.
7. The main method demonstrates the function with various test cases.

Time Complexity: O(N\*M), where N and M are the lengths of the two arrays. This approach is simple but can be inefficient for very large arrays.

Approach 2: Using a HashSet

Summary: This approach leverages the efficient lookup capabilities of a HashSet. All elements of one array are added to a HashSet. Then, each element of the second array is checked against the HashSet. If an element from the second array is found in the set, the arrays are not disjoint.

// DisjointArrayHashSet
import java.util.HashSet;
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    /**
     * Checks if two integer arrays are disjoint using a HashSet.
     * @param arr1 The first array.
     * @param arr2 The second array.
     * @return true if the arrays are disjoint (no common elements), false otherwise.
     */
    public static boolean areArraysDisjointHashSet(int[] arr1, int[] arr2) {
        // Step 1: Create a HashSet to store elements from the first array.
        HashSet<Integer> set = new HashSet<>();

        // Step 2: Add all elements of arr1 to the HashSet.
        for (int element : arr1) {
            set.add(element);
        }

        // Step 3: Iterate through each element of the second array.
        for (int element : arr2) {
            // Step 4: Check if the current element from arr2 exists in the HashSet.
            if (set.contains(element)) {
                // Step 5: If it exists, a common element is found, so arrays are not disjoint.
                return false;
            }
        }
        // Step 6: If no common elements are found after checking all elements of arr2, the arrays are disjoint.
        return true;
    }

    public static void main(String[] args) {
        // Test Case 1: Disjoint arrays
        int[] arr1_case1 = {1, 2, 3};
        int[] arr2_case1 = {4, 5, 6};
        System.out.println("Arrays: {1, 2, 3} and {4, 5, 6}");
        System.out.println("Are disjoint (HashSet)? " + areArraysDisjointHashSet(arr1_case1, arr2_case1)); // Expected: true

        // Test Case 2: Non-disjoint arrays
        int[] arr1_case2 = {1, 2, 3};
        int[] arr2_case2 = {3, 4, 5};
        System.out.println("\\nArrays: {1, 2, 3} and {3, 4, 5}");
        System.out.println("Are disjoint (HashSet)? " + areArraysDisjointHashSet(arr1_case2, arr2_case2)); // Expected: false

        // Test Case 3: Empty arrays
        int[] arr1_case3 = {};
        int[] arr2_case3 = {1, 2, 3};
        System.out.println("\\nArrays: {} and {1, 2, 3}");
        System.out.println("Are disjoint (HashSet)? " + areArraysDisjointHashSet(arr1_case3, arr2_case3)); // Expected: true
    }
}

Run

Sample Output:

Arrays: {1, 2, 3} and {4, 5, 6}
Are disjoint (HashSet)? true

Arrays: {1, 2, 3} and {3, 4, 5}
Are disjoint (HashSet)? false

Arrays: {} and {1, 2, 3}
Are disjoint (HashSet)? true

Stepwise Explanation:

1. A HashSet named set is initialized.
2. All elements from arr1 are added to set. Adding elements to a HashSet takes average O(1) time.
3. Then, the code iterates through each element in arr2.
4. For each element in arr2, set.contains(element) is called. contains() operation on a HashSet takes average O(1) time.
5. If set.contains(element) returns true, it means a common element has been found, and the method immediately returns false.
6. If the loop completes without finding any common elements, the arrays are disjoint, and the method returns true.

Time Complexity: Average O(N + M), where N and M are the lengths of the two arrays. This is significantly more efficient than the brute-force approach for larger arrays. Space Complexity: O(N) to store elements from the first array in the HashSet.

Approach 3: Sorting and Two Pointers

Summary: This method involves sorting both arrays first. Once sorted, two pointers are used, one for each array, to traverse them simultaneously. If elements at the pointers match, a common element is found.

// DisjointArraySortAndPointers
import java.util.Arrays;
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    /**
     * Checks if two integer arrays are disjoint by sorting and using two pointers.
     * @param arr1 The first array.
     * @param arr2 The second array.
     * @return true if the arrays are disjoint (no common elements), false otherwise.
     */
    public static boolean areArraysDisjointSortAndPointers(int[] arr1, int[] arr2) {
        // Step 1: Sort both arrays.
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        // Step 2: Initialize two pointers, one for each array.
        int i = 0; // Pointer for arr1
        int j = 0; // Pointer for arr2

        // Step 3: Iterate while both pointers are within their respective array bounds.
        while (i < arr1.length && j < arr2.length) {
            // Step 4: If elements at current pointers are equal, a common element is found.
            if (arr1[i] == arr2[j]) {
                return false; // Not disjoint
            }
            // Step 5: If element in arr1 is smaller, move arr1's pointer forward.
            else if (arr1[i] < arr2[j]) {
                i++;
            }
            // Step 6: If element in arr2 is smaller, move arr2's pointer forward.
            else { // arr1[i] > arr2[j]
                j++;
            }
        }
        // Step 7: If the loops complete without finding any common elements, the arrays are disjoint.
        return true;
    }

    public static void main(String[] args) {
        // Test Case 1: Disjoint arrays
        int[] arr1_case1 = {1, 3, 2}; // Unsorted initially
        int[] arr2_case1 = {6, 4, 5}; // Unsorted initially
        System.out.println("Arrays: {1, 3, 2} and {6, 4, 5}");
        System.out.println("Are disjoint (Sort & Pointers)? " + areArraysDisjointSortAndPointers(arr1_case1, arr2_case1)); // Expected: true

        // Test Case 2: Non-disjoint arrays
        int[] arr1_case2 = {2, 1, 3}; // Unsorted initially
        int[] arr2_case2 = {5, 3, 4}; // Unsorted initially
        System.out.println("\\nArrays: {2, 1, 3} and {5, 3, 4}");
        System.out.println("Are disjoint (Sort & Pointers)? " + areArraysDisjointSortAndPointers(arr1_case2, arr2_case2)); // Expected: false

        // Test Case 3: Empty arrays
        int[] arr1_case3 = {};
        int[] arr2_case3 = {1, 2, 3};
        System.out.println("\\nArrays: {} and {1, 2, 3}");
        System.out.println("Are disjoint (Sort & Pointers)? " + areArraysDisjointSortAndPointers(arr1_case3, arr2_case3)); // Expected: true
    }
}

Run

Sample Output:

Arrays: {1, 3, 2} and {6, 4, 5}
Are disjoint (Sort & Pointers)? true

Arrays: {2, 1, 3} and {5, 3, 4}
Are disjoint (Sort & Pointers)? false

Arrays: {} and {1, 2, 3}
Are disjoint (Sort & Pointers)? true

Stepwise Explanation:

1. Both arr1 and arr2 are sorted using Arrays.sort().
2. Two pointers, i and j, are initialized to 0, pointing to the start of arr1 and arr2 respectively.
3. A while loop continues as long as both pointers are within the bounds of their arrays.
4. Inside the loop, the elements at arr1[i] and arr2[j] are compared:

• If arr1[i] == arr2[j], a common element is found, and the method returns false.
• If arr1[i] < arr2[j], it means arr1[i] cannot be equal to any subsequent elements in arr2 (because arr2 is sorted and its elements will only be greater or equal). So, i is incremented.
• If arr1[i] > arr2[j], it means arr2[j] cannot be equal to any subsequent elements in arr1. So, j is incremented.

1. If the loop completes without returning false, it means no common elements were found, and the arrays are disjoint, so the method returns true.

Time Complexity: O(N log N + M log M) due to the sorting step, followed by O(N + M) for the two-pointer traversal. This is efficient for large arrays and can be a good alternative if sorting the arrays is acceptable or already done. Space Complexity: O(1) if sorting is in-place, or O(log N) to O(N) depending on the sort implementation's auxiliary space.

Conclusion

We've explored three distinct approaches for checking if two arrays are disjoint in Java: brute-force, HashSet-based, and sort-and-two-pointers. Each method offers different trade-offs in terms of time and space complexity.

• The brute-force method is straightforward to implement but is the least efficient for large arrays (O(N\*M)).
• The HashSet approach offers significant performance improvements (average O(N+M)) by utilizing constant-time average lookups, but it incurs additional space complexity (O(N)).
• The sorting and two-pointers method provides a good balance (O(N log N + M log M) time, O(1) auxiliary space if sort is in-place), especially if the arrays are already sorted or if memory usage is a critical concern over raw speed.

Choosing the best approach depends on the specific constraints of your application, including array sizes, frequency of checks, and available memory.

Summary

• Disjoint Arrays: Two arrays are disjoint if they share no common elements.
• Brute-Force:
• Compares every element of arr1 with every element of arr2.
• Time Complexity: O(N\*M)
• Simple, but inefficient for large arrays.
• HashSet Approach:
• Adds all elements of one array to a HashSet.
• Iterates through the second array, checking for existence in the HashSet.
• Time Complexity: Average O(N+M)
• Space Complexity: O(N)
• Highly efficient for large arrays, but uses additional memory.
• Sorting and Two-Pointers:
• Sorts both arrays.
• Uses two pointers to traverse sorted arrays, looking for matches.
• Time Complexity: O(N log N + M log M)
• Space Complexity: O(1) (for in-place sort)
• Good for large arrays when memory is constrained or sorting is permissible.