Check if Two Arrays are Disjoint

Title: Check if Two Arrays are Disjoint

In this guide, you’ll learn how to check whether two arrays are disjoint, meaning they share no common elements. This is a frequent interview warm-up question that tests whether you reach for a Set instead of writing nested loops. We’ll build a clean HashSet-based solution, trace it on a sample input, and cover the edge cases and follow-up questions interviewers like to ask.

Understanding the Problem

Two arrays are disjoint when no value present in the first array also appears in the second array. For example, {1, 2, 3} and {4, 5, 6} are disjoint, but {1, 2, 3} and {3, 4, 5} are not, because 3 appears in both.

The naive approach compares every element of arr1 against every element of arr2, which costs O(n * m) time. A HashSet lets us check membership in roughly O(1) time, bringing the whole check down to O(n + m).

Approach / Algorithm Steps

Here’s the step-by-step approach we’ll implement:

1. Create an empty HashSet<Integer> named seen to hold the elements of the first array.
2. Iterate over arr1 and add every element into seen.
3. Iterate over arr2, and for each element check whether seen already contains it.
4. If seen contains the current element of arr2, the arrays share a value, so return false immediately.
5. If the loop over arr2 completes without finding a match, no shared elements exist, so return true.

Java Program

Here’s the full, compilable program. The core logic lives in areDisjoint, which the main method exercises with a couple of sample inputs.

import java.util.HashSet;
import java.util.Set;

public class CheckDisjointArrays {

    public static boolean areDisjoint(int[] arr1, int[] arr2) {
        Set<Integer> seen = new HashSet<>();
        for (int value : arr1) {
            seen.add(value);
        }
        for (int value : arr2) {
            if (seen.contains(value)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {6, 7, 8, 9, 10};
        int[] arr3 = {4, 5, 6};

        System.out.println("arr1 and arr2 disjoint: " + areDisjoint(arr1, arr2));
        System.out.println("arr1 and arr3 disjoint: " + areDisjoint(arr1, arr3));
    }
}

Explanation of the Program

• seen is a HashSet<Integer> that stores every value from arr1 for fast lookups.
• The first for loop populates seen by adding each element of arr1.
• The second for loop walks arr2 and calls seen.contains(value) to test membership.
• As soon as a shared value is found, the method returns false without scanning the rest of arr2.
• If no match is found after the full scan, the method returns true, confirming the arrays are disjoint.

Step-by-Step Trace

For arr1 = {2, 4, 6} and arr2 = {1, 3, 6, 8}, the expected output is false, because 6 is shared. After the first loop builds seen = {2, 4, 6}, the second loop walks arr2 as follows:

At the end of each iteration that does not trigger a match, every value of arr2 checked so far is confirmed absent from seen.

Examples

These examples cover a fully disjoint pair, an overlapping pair, and an empty-array input.

Example 1: Fully Disjoint Arrays

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {6, 7, 8, 9, 10};
System.out.println(areDisjoint(arr1, arr2));
// Output: true

Example 2: Arrays with a Shared Element

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {4, 5, 6};
System.out.println(areDisjoint(arr1, arr2));
// Output: false

Example 3: One Array is Empty

int[] arr1 = {};
int[] arr2 = {1, 2, 3};
System.out.println(areDisjoint(arr1, arr2));
// Output: true

Common Mistakes to Avoid

These are the mistakes candidates most often make when solving this problem.

• Comparing with nested loops – checking every element of arr1 against every element of arr2 runs in O(n * m) time and times out on large inputs. Use a HashSet to bring this down to O(n + m).
• Comparing array lengths instead of contents – assuming arrays of different sizes must be disjoint ignores that disjointness depends on shared values, not size. Always check the actual elements.
• Merging both arrays into one Set and checking size – adding every element of both arrays into a single Set and comparing its size to the combined length looks clever but gives a false positive whenever either array has internal duplicates. Keep the two scanning phases separate.
• Sorting the input arrays in place – calling Arrays.sort(arr1) to enable a two-pointer scan mutates the caller’s original array unexpectedly. Sort a copy if the input must stay unchanged.

Edge Cases to Test

Walk through these inputs before calling the solution complete.

• Empty first array
• Empty second array
• Both arrays empty
• Identical arrays
• Duplicate values within a single array
• Single-element arrays
• Negative numbers
• Integer.MIN_VALUE / Integer.MAX_VALUE present

Additional Considerations

The HashSet approach runs in O(n + m) time, where n and m are the lengths of arr1 and arr2. It uses O(n) extra space for the seen set.

If the arrays are already sorted, a two-pointer scan achieves the same O(n + m) time bound using O(1) extra space instead of a Set, trading a sorting precondition for lower memory use.

Because HashSet.contains relies on hashCode and equals, boxed Integer values work correctly out of the box, but a custom object type would need both methods implemented correctly for the lookup to behave as expected.

Interview Follow-up Questions

Once you’ve nailed the base solution, expect one of these variants next.

• What if the arrays are already sorted? – use a two-pointer scan that advances whichever pointer points at the smaller value; a match means the arrays are not disjoint.
• What if you need the actual common elements, not just a yes/no answer? – keep the same seen set, but instead of returning early, collect every matching value into a result list.
• What if the arrays are too large to fit in memory? – sort each array externally in chunks and merge-scan them from disk, or use a probabilistic Bloom filter to rule out most lookups before confirming with an exact check.
• What if you must test one fixed array against many other arrays? – build the HashSet for the fixed array once and reuse it across every disjointness check instead of rebuilding it each time.

Conclusion

Checking whether two arrays are disjoint comes down to one idea: trade a slow pairwise comparison for a fast Set lookup. The HashSet solution runs in O(n + m) time and handles duplicates and empty arrays correctly, which makes it a clean fit for an interview setting.

Try adapting this code to return the shared elements instead of a boolean, or to work with sorted input using two pointers. You can learn more about array algorithms in the Arrays category on dailyjavaconcept.com.