Intersection of Two Unsorted Arrays

Given two unsorted arrays a (length m) and b (length n), return their intersection: the distinct values present in both. The order doesn't matter.

LeetCode: 349. Intersection of Two Arrays

Example

Text

Input:  a = [1, 4, 3, 2, 5, 8, 9], b = [6, 3, 2, 7, 5]
Output: [3, 2, 5]

Input:  a = [3, 4, 6, 7, 10, 12, 5], b = [7, 11, 18, 15, 12]
Output: [7, 12]

Brute force: nested scans

For each value of a, search b for it, and skip values already in the result.

Java

import java.util.ArrayList;
import java.util.List;

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

    static List<Integer> intersection(int[] a, int[] b) {
        List<Integer> result = new ArrayList<>();
        for (int x : a) {
            if (contains(b, x) && !result.contains(x)) {
                result.add(x);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(intersection(new int[]{1, 4, 3, 2, 5, 8, 9}, new int[]{6, 3, 2, 7, 5}));
        System.out.println(intersection(new int[]{3, 4, 6, 7, 10, 12, 5}, new int[]{7, 11, 18, 15, 12}));
    }
}

Output

[3, 2, 5]
[7, 12]

Time: O(m·n), plus O(m·k) for the result.contains calls on a result of size k. Space: O(1) besides the output.

Sorting both arrays and walking them with two pointers (advance the smaller side, record equal values once) brings this to O(m log m + n log n) time with no hashing.

Optimal: a HashSet

Put the values of b into a set. Walk a, and output each value found in the set. Removing it from the set as it's output handles duplicates in a.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static List<Integer> intersection(int[] a, int[] b) {
        Set<Integer> inB = new HashSet<>();
        for (int x : b) inB.add(x);
        List<Integer> result = new ArrayList<>();
        for (int x : a) {
            if (inB.remove(x)) result.add(x); // true only the first time x is removed
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(intersection(new int[]{1, 4, 3, 2, 5, 8, 9}, new int[]{6, 3, 2, 7, 5}));
        System.out.println(intersection(new int[]{3, 4, 6, 7, 10, 12, 5}, new int[]{7, 11, 18, 15, 12}));
        System.out.println(intersection(new int[]{1, 2, 2, 1}, new int[]{2, 2}));
        System.out.println(intersection(new int[]{1, 2}, new int[]{3, 4}));
    }
}

Output

[3, 2, 5]
[7, 12]
[2]
[]

Time: O(m + n) on average. Space: O(n). Building the set from the smaller array keeps the space at O(min(m, n)).

Set.remove returns true only the first time a value is removed, so it is both the membership test and the duplicate filter. The result is a List<Integer> in the order the values appear in a. List.contains and Set.remove take an Object, so the int is boxed to an Integer and compared with equals.

Edge cases

No common values or an empty array: an empty result.
Keeping duplicates (LeetCode 350): count b in a HashMap<Integer, Integer> and output a value of a while its count is above zero, decrementing each time.