Check if Two Arrays Are Disjoint: C, C++, Java and Python

Two arrays are disjoint if they have no elements in common, and the most efficient check drops from O(m×n) with nested loops to O(m+n) with a hash set.

The brute-force solution appears in placement test coding rounds and is easy to understand. The hash-set solution is what a tech interview panel expects for any input beyond a few dozen elements. This article covers all three practical approaches, with complete code in C, C++, Java, and Python.

What Makes Two Arrays Disjoint

Two arrays are disjoint when their intersection is empty. Concretely:

• Disjoint pair: arr1 = {1, 2, 3, 4, 5} and arr2 = {6, 7, 8, 9} share no elements.
• Non-disjoint pair: arr1 = {1, 2, 3, 4, 5} and arr2 = {4, 5, 6, 7} share elements 4 and 5.

Two edge cases are worth knowing before writing any implementation:

• Empty arrays: if either array is empty, the result is trivially disjoint. No iteration is needed and no implementation should crash on empty input.
• Duplicates within one array: arr1 = {1, 1, 2, 3} and arr2 = {4, 5} are still disjoint. Duplicate values inside a single array do not affect whether the two arrays share any element.

The problem maps directly to what data structures questions in placement rounds test: can you pick the right data structure for the operation?

Method 1: Nested Loops

The nested-loop approach uses no extra memory. An outer loop walks arr1 and an inner loop walks arr2. If any pair of elements matches, return false immediately.

Time complexity: O(m×n), where m is the size of arr1 and n is the size of arr2. Space complexity: O(1).

C

#include <stdio.h>
#include <stdbool.h>

bool areDisjoint(int arr1[], int m, int arr2[], int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr1[i] == arr2[j]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {6, 7, 8, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    printf("%s\n", areDisjoint(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint");
    return 0;
}

C++

#include <iostream>
using namespace std;

bool areDisjoint(int arr1[], int m, int arr2[], int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr1[i] == arr2[j]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {6, 7, 8, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    cout << (areDisjoint(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint") << endl;
    return 0;
}

Java

public class DisjointArrays {
    static boolean areDisjoint(int[] arr1, int[] arr2) {
        for (int x : arr1) {
            for (int y : arr2) {
                if (x == y) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {6, 7, 8, 9};
        System.out.println(areDisjoint(arr1, arr2) ? "Disjoint" : "Not disjoint");
    }
}

Python

def are_disjoint_brute(arr1, arr2):
    for x in arr1:
        for y in arr2:
            if x == y:
                return False
    return True

arr1 = [1, 2, 3, 4, 5]
arr2 = [6, 7, 8, 9]
print("Disjoint" if are_disjoint_brute(arr1, arr2) else "Not disjoint")

The nested-loop version works correctly, but its cost grows with both array sizes. Consider the scaling trade-off:

• Two arrays of 200 elements each: up to 40,000 comparisons in the worst case.
• Two arrays of 10,000 elements each: up to 100 million comparisons in the worst case.

The hash-set method below handles the same input with two linear passes through the arrays.

Method 2: Sort and Two-Pointer

Sort both arrays, then use two index pointers to scan them in a single pass, using the same merge step as merge sort.

Algorithm:

• Sort arr1 in ascending order.
• Sort arr2 in ascending order.
• Use two indices i and j starting at 0.
• If arr1[i] < arr2[j], increment i.
• If arr1[i] > arr2[j], increment j.
• If arr1[i] == arr2[j], a common element exists; return false.
• If either pointer reaches the end without a match, return true.

Time complexity: O(m log m + n log n) for sorting, plus O(m+n) for the scan. Dominant term: O((m+n) log(m+n)). Space complexity: O(1) extra (sorting done in place with std::sort or qsort).

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

bool areDisjointSorted(int arr1[], int m, int arr2[], int n) {
    qsort(arr1, m, sizeof(int), compare);
    qsort(arr2, n, sizeof(int), compare);

    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])      i++;
        else if (arr1[i] > arr2[j]) j++;
        else                         return false;
    }
    return true;
}

int main() {
    int arr1[] = {5, 3, 1, 4, 2};
    int arr2[] = {9, 7, 6, 8};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    printf("%s\n", areDisjointSorted(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint");
    return 0;
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

bool areDisjointSorted(int arr1[], int m, int arr2[], int n) {
    sort(arr1, arr1 + m);
    sort(arr2, arr2 + n);

    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])      i++;
        else if (arr1[i] > arr2[j]) j++;
        else                         return false;
    }
    return true;
}

int main() {
    int arr1[] = {5, 3, 1, 4, 2};
    int arr2[] = {9, 7, 6, 8};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    cout << (areDisjointSorted(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint") << endl;
    return 0;
}

Java

import java.util.Arrays;

public class DisjointSorted {
    static boolean areDisjoint(int[] arr1, int[] arr2) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j])      i++;
            else if (arr1[i] > arr2[j]) j++;
            else                         return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = {5, 3, 1, 4, 2};
        int[] arr2 = {9, 7, 6, 8};
        System.out.println(areDisjoint(arr1, arr2) ? "Disjoint" : "Not disjoint");
    }
}

Python

def are_disjoint_sorted(arr1, arr2):
    arr1 = sorted(arr1)
    arr2 = sorted(arr2)
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            i += 1
        elif arr1[i] > arr2[j]:
            j += 1
        else:
            return False
    return True

arr1 = [5, 3, 1, 4, 2]
arr2 = [9, 7, 6, 8]
print("Disjoint" if are_disjoint_sorted(arr1, arr2) else "Not disjoint")

This approach is most useful when the arrays arrive pre-sorted (no sort cost) or when memory is constrained and you cannot afford the hash set’s O(m) extra space.

Method 3: Hash Set

Build a hash set from arr1, then check each element of arr2 for membership. Hash-set lookup is O(1) average, so the total scan over arr2 costs O(n) average after an O(m) build step.

Time complexity: O(m+n) average. Space complexity: O(m) for the hash set.

C

C has no built-in hash set. For integer values in a known bounded range, a boolean-array lookup achieves the same O(1) membership test. The example below works for non-negative integer values within the range defined by the MAX_VAL constant.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_VAL 10001

bool areDisjointHash(int arr1[], int m, int arr2[], int n) {
    bool seen[MAX_VAL];
    memset(seen, false, sizeof(seen));

    for (int i = 0; i < m; i++) {
        seen[arr1[i]] = true;
    }
    for (int j = 0; j < n; j++) {
        if (seen[arr2[j]]) return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {6, 7, 8, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    printf("%s\n", areDisjointHash(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint");
    return 0;
}

For general integer values (including negatives or values beyond a fixed range), replace the boolean array with a proper hash table. Most competitive-programming judges accept the boolean-array version when constraints are stated.

C++

C++ provides std::unordered_set in <unordered_set>, which offers O(1) average insert and lookup per the cppreference documentation.

#include <iostream>
#include <unordered_set>
using namespace std;

bool areDisjointHash(int arr1[], int m, int arr2[], int n) {
    unordered_set<int> seen(arr1, arr1 + m);
    for (int j = 0; j < n; j++) {
        if (seen.count(arr2[j])) return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {6, 7, 8, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    cout << (areDisjointHash(arr1, m, arr2, n) ? "Disjoint" : "Not disjoint") << endl;
    return 0;
}

The constructor unordered_set<int> seen(arr1, arr1 + m) builds the set in one call. seen.count(x) returns 1 if the element is present, 0 otherwise.

Java

Java’s HashSet<Integer> from java.util provides the same O(1) average operations. The Java SE 8 HashSet documentation confirms average constant-time performance for add and contains.

import java.util.HashSet;

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

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {6, 7, 8, 9};
        System.out.println(areDisjoint(arr1, arr2) ? "Disjoint" : "Not disjoint");
    }
}

Python

Python’s built-in set type has O(1) average membership lookup. The standard library provides set.isdisjoint(other), which returns True if the two sets share no elements.

def are_disjoint(arr1, arr2):
    return set(arr1).isdisjoint(arr2)

arr1 = [1, 2, 3, 4, 5]
arr2 = [6, 7, 8, 9]
print("Disjoint" if are_disjoint(arr1, arr2) else "Not disjoint")

isdisjoint accepts any iterable as its argument, so passing arr2 directly (without converting it to a set first) is valid and still runs in O(n) average time.

Complexity Comparison and Choosing an Approach

The right method depends on array size, whether the input arrives sorted, and available memory.

Method	Time (average)	Space	Best used when
Nested loops	O(m×n)	O(1)	Arrays are tiny (under 200 elements each)
Sort + two-pointer	O((m+n) log(m+n))	O(1) extra	Arrays arrive pre-sorted, or memory is very tight
Hash set	O(m+n)	O(m)	Arrays are unsorted and values are not bounded
Boolean array (C)	O(m+n)	O(range)	C environment, values bounded to a known range

For placement test coding rounds, the hash-set solution is the expected answer when no constraint says “without extra space.” Interviewers typically ask for the O(m+n) version first, then ask for the O(1) space alternative as a follow-up.

Linear array traversal patterns, including the outer loop in Method 1 and the two-pointer scan in Method 2, are the same patterns that appear in finding the minimum and maximum element in a single pass. Recognising the shared structure helps when an interview question combines multiple traversal requirements.

The hash-set approach that cuts this check from O(m×n) to O(m+n) is the same lookup-once-per-query principle behind retrieval-augmented generation (RAG) in LLM systems: build an index from a knowledge base once, then probe it for each input query in constant time. TinkerLLM lets you build a working RAG pipeline at ₹299 and see that O(1) lookup logic operating at the token level.