Check if Two Arrays Are Disjoint

Given two arrays, return true if they are disjoint, meaning no value appears in both.

Example 1

Text

a = [1, 2, 3], b = [4, 5, 6]
Output: true

Example 2

Text

a = [1, 2, 3], b = [3, 4, 5]
Output: false   (3 is in both)

Brute force: compare every pair

Java

public class Main {
    static boolean isDisjoint(int[] a, int[] b) {
        for (int x : a) {
            for (int y : b) {
                if (x == y) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isDisjoint(new int[]{1, 2, 3}, new int[]{4, 5, 6}) + " " + isDisjoint(new int[]{1, 2, 3}, new int[]{3, 4, 5}));
    }
}

Output

true false

Time: O(n·m). Space: O(1).

Better: sort both, then walk with two pointers

After sorting, walk both arrays like a merge. If the current values are equal, the arrays share a value. Otherwise, advance the pointer at the smaller value.

Java

import java.util.Arrays;

public class Main {
    static boolean isDisjoint(int[] a, int[] b) {
        int[] x = a.clone();
        int[] y = b.clone();
        Arrays.sort(x);
        Arrays.sort(y);
        int i = 0, j = 0;
        while (i < x.length && j < y.length) {
            if (x[i] == y[j]) {
                return false;
            } else if (x[i] < y[j]) {
                i++;
            } else {
                j++;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isDisjoint(new int[]{1, 2, 3}, new int[]{4, 5, 6}) + " " + isDisjoint(new int[]{3, 1, 2}, new int[]{5, 4, 3}));
    }
}

Output

true false

Time: O(n log n + m log m). Space: O(n + m) for the copies, or O(1) extra if the inputs may be sorted in place.

Optimal: hash the smaller array

Put the smaller array into a HashSet (less memory), then check each element of the larger one.

Walkthrough with a = [1, 2, 3], b = [3, 4, 5]. Both have 3 elements, so hash a: the set is {1, 2, 3}.

element of b	in set?
3	yes → return `false`

Java

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

public class Main {
    static boolean isDisjoint(int[] a, int[] b) {
        int[] small = a.length <= b.length ? a : b;
        int[] large = a.length <= b.length ? b : a;
        Set<Integer> set = new HashSet<>();
        for (int x : small) set.add(x);
        for (int x : large) {
            if (set.contains(x)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isDisjoint(new int[]{1, 2, 3}, new int[]{4, 5, 6}) + " " + isDisjoint(new int[]{1, 2, 3}, new int[]{3, 4, 5}));
        System.out.println(isDisjoint(new int[]{}, new int[]{1}));
    }
}

Output

true false
true

Time: O(n + m). Space: O(min(n, m)).

HashSet<Integer> stores boxed Integer objects, so each int of small is wrapped once.

For two collections, Collections.disjoint(c1, c2) returns true when they share no element. It is a library method, so the arrays must first be converted to collections.

Edge cases

Either array empty: disjoint (true).
Duplicates: don't matter. One shared value is enough to return false.