Intersection of Two Arrays

Easy Arrays & Hashing Two Pointer Original on LeetCode

Intersection of Two Arrays is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (hash set), runs in O(n + m) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

Given two integer arrays nums1 and nums2, return an array of the values that appear in both of them.

Each value in the result must be unique, even if it occurs several times in either input. The result can be returned in any order.

Examples

Example 1

Input
nums1 = [3, 8, 8, 1, 6], nums2 = [6, 2, 8, 6]
Output
[8, 6]
Why
8 and 6 appear in both arrays. Each is reported once, no matter how often it repeats.

Example 2

Input
nums1 = [5, 5, 5], nums2 = [5]
Output
[5]
Why
The only shared value is 5, listed a single time.

Example 3

Input
nums1 = [2, 4], nums2 = [1, 3, 7]
Output
[]
Why
No value appears in both arrays.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  • Every value in the result must be unique; the result may be in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n · m)O(1)
Sort + two pointersO(n log n + m log m)O(1)
Optimal (hash set)O(n + m)O(n)

1Brute force

TimeO(n · m)Each of the n values of nums1 may scan all m values of nums2 (plus the small answer list).
SpaceO(1)Only the output list.

For every value of nums1, scan nums2 for it. Before scanning, skip values already in the answer so nothing is reported twice.

  1. For each x in nums1: if x is already in res, skip it.
  2. Scan nums2; if some y == x, add x to res and stop scanning.
  3. Return res as an array.
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> res = new ArrayList<>();
        for (int x : nums1) {
            if (res.contains(x)) continue;
            for (int y : nums2) {
                if (x == y) {
                    res.add(x);
                    break;
                }
            }
        }
        int[] out = new int[res.size()];
        for (int i = 0; i < out.length; i++) out[i] = res.get(i);
        return out;
    }
}

2Sort + two pointers

TimeO(n log n + m log m)Sorting dominates; the merge walk is O(n + m).
SpaceO(1)Apart from the output and the sort's own workspace.

Sort both arrays. Walk them with one pointer each: move the pointer at the smaller value forward; on a match, record the value (unless it equals the last recorded one) and move both pointers.

  1. Sort nums1 and nums2.
  2. i = j = 0.
  3. If nums1[i] < nums2[j], i++; if greater, j++.
  4. If equal: add it when res is empty or its last value differs, then i++ and j++.
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] a = nums1.clone(), b = nums2.clone();
        Arrays.sort(a);
        Arrays.sort(b);
        List<Integer> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                i++;
            } else if (a[i] > b[j]) {
                j++;
            } else {
                if (res.isEmpty() || res.get(res.size() - 1) != a[i]) res.add(a[i]);
                i++;
                j++;
            }
        }
        int[] out = new int[res.size()];
        for (int k = 0; k < out.length; k++) out[k] = res.get(k);
        return out;
    }
}

3Optimal (hash set)

TimeO(n + m)Each value is inserted, looked up or removed once, in O(1) on average.
SpaceO(n)The set holds the distinct values of nums1.

Load nums1 into a set. Walk nums2: whenever a value is in the set, add it to the answer and remove it from the set, so a repeated value in nums2 is never reported twice.

  1. seen = set of all values in nums1.
  2. For each y in nums2: if seen contains y, add y to res and remove y from seen.
  3. Return res.
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums1) seen.add(x);
        List<Integer> res = new ArrayList<>();
        for (int y : nums2) {
            if (seen.remove(y)) res.add(y);
        }
        int[] out = new int[res.size()];
        for (int i = 0; i < out.length; i++) out[i] = res.get(i);
        return out;
    }
}

Edge cases to test

  • No common values: return an empty array
  • Heavy duplicates in one or both arrays
  • One array is a single element
  • Both arrays identical
  • The value 0

Hints

Hint 1

For each value of nums1 you need a fast answer to: does it occur anywhere in nums2?

Hint 2

Put one array's values into a set. Then make sure each shared value is reported only once.

Hint 3

Alternatively, sort both arrays and walk them together with two pointers, skipping repeats.

FAQ

What is the best time complexity for Intersection of Two Arrays?

Optimal (hash set) runs in O(n + m) time and O(n) extra space. Each value is inserted, looked up or removed once, in O(1) on average.

Which pattern does Intersection of Two Arrays use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Intersection of Two Arrays?

Yes. Brute force takes O(n · m) time and O(1) space. For every value of nums1, scan nums2 for it.

Which edge cases should I test for Intersection of Two Arrays?

No common values: return an empty array; Heavy duplicates in one or both arrays; One array is a single element; Both arrays identical; The value 0.