Intersection of Two Arrays

Q: What is the time complexity of Intersection of Two Arrays?

With a hash set, finding the shared values takes O(n + m) on average and sorting the k values of the answer adds O(k log k) ; the set uses O(n) space. Sorting both arrays and walking them with two pointers takes O(n log n + m log m) . Comparing every pair takes O(n × m) .

EasyHashing

+10

You get two arrays of integers, nums1 and nums2. Return every value that appears in both arrays, sorted in increasing order. Each shared value appears in the answer once, however many times it repeats in either array.

Function

intersection(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: the first list of integers
nums2integer-array: the second list of integers
Returnsinteger-array: the values found in both lists, each once, in increasing order

Constraints

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
At least one value appears in both arrays.

Examples

Input: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Output: [4, 6]
Explanation: 4 and 6 are in both arrays. 4 appears twice in nums2 but is listed once, and 2 and 9 never appear in nums2.

Input: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Output: [-3, 7]
Explanation: -3 and 7 are in both arrays. In increasing order -3 comes first, even though 7 comes first in nums2.

+16 hidden tests on Submit

Follow-up

What if nums1 holds 10 values and nums2 holds a million, already sorted? Which approach would you pick, and can binary search beat a full walk?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Two details decide this problem: a value that repeats on both sides still goes in the answer once, and the answer must come out sorted. Comparing every pair works but costs n × m comparisons, 2.5 × 10^7 when both arrays hold 5000 values. Sorting both arrays lets two pointers meet the shared values in order, and a hash set of one array answers "is this value in nums1?" in constant time.

Compare every pair

Correct, but does not finish on the largest tests

Intuition

Take each value of nums1 and scan nums2 for it. Stop the scan at the first match, and skip a value that is already in the answer, so [8, 8, 8, 8] against [8, 8] gives one 8, not four. Sort the answer at the end.

It is correct because a value goes in the answer exactly when some copy of it in nums1 finds a match in nums2, and the skip keeps it from going in twice.

It is slow because each value of nums1 may scan all of nums2. With 5000 values in each array that is up to 2.5 × 10^7 comparisons, and on the large tests most values find no match, so most scans run to the end.

Algorithm

Start with an empty answer list.
For each value a in nums1, skip it if it is already in the answer.
Otherwise scan nums2; at the first value equal to a, add a to the answer and stop the scan.
Sort the answer in increasing order and return it.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Sort both, then walk with two pointers

Intuition

Sorted, example 1 becomes [2, 2, 4, 6, 9] and [1, 4, 4, 6]. Put pointer i at the start of the first array and j at the start of the second. The pointer on the smaller value moves forward: that value cannot match anything further along the other array, where every value is at least as large. When both pointers see the same value, it is shared, so add it and move both.

On the example: 2 > 1 moves j, both 2s are smaller than 4 and move i, 4 = 4 adds 4, the second 4 is smaller than 6 and moves j, and 6 = 6 adds 6. A value shared several times on both sides, like 2 in [2, 2, 3] and [2, 2], matches more than once; comparing it with the last value added keeps one copy. The answer comes out sorted with no extra step.

Sorting costs O(n log n + m log m), and the walk is O(n + m) because every step moves at least one pointer. Most versions sort copies, which costs O(n + m) memory. If you may reorder the inputs, sort them in place, as the C code does, and the only extra memory is the answer.

Algorithm

Sort both arrays.
Set i = 0 and j = 0.
While both pointers are inside their arrays, move the pointer at the smaller value.
On equal values, add the value unless it equals the last value added, then move both pointers.
Return the answer.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Hash set of the first array

Intuition

Put every value of nums1 in a hash set. In example 1 the set is {6, 2, 9, 4}: the repeated 2 collapses on the way in. Then walk nums2 and ask the set about each value in constant time. The first 4 is there, so it goes in the answer. The second 4 must not, so you remove a value from the set the moment it matches. 1 is not there and 6 is, which gives [4, 6].

Removing on a match is what keeps each value once: after its first match a value is gone from the set, so later copies in nums2 find nothing. Every value added is in both arrays, and every shared value is added when its first copy in nums2 arrives.

Building the set and the walk take O(n + m) on average. The answer comes out in the order of nums2, so sort it at the end; it holds k ≤ min(n, m) values, which costs O(k log k). C has no built-in set, so the C code uses a flag array indexed by value + 10^5, which works because the values are bounded.

Algorithm

Build a hash set first from nums1.
For each value in nums2, if it is in first, add it to the answer and remove it from first.
Sort the answer in increasing order.
Return it.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Pitfalls and edge cases

Most wrong answers here come from repeated values and from the order of the output.

Adding a value every time it matches. [2, 2, 3, 3, 3] and [3, 2, 2] share two values, so the answer is [2, 3], not [3, 2, 2].
Returning the values in the order you found them. The hash set walk follows nums2, so [7, -3] must still be sorted to [-3, 7].
Sorting numbers as text. JavaScript's sort() without a comparator compares strings, so [100000, 99] stays in that order. Pass (x, y) => x - y.
Using a set intersection and forgetting the order. Python's set(nums1) & set(nums2) finds the right values in no particular order; wrap it in sorted.
Indexing a flag array by the raw value. -3 is not a valid index; shift every value by 10^5 first.

Frequently asked questions4

What is the time complexity of Intersection of Two Arrays?

With a hash set, finding the shared values takes O(n + m) on average and sorting the k values of the answer adds O(k log k); the set uses O(n) space. Sorting both arrays and walking them with two pointers takes O(n log n + m log m). Comparing every pair takes O(n × m).

Should you use a hash set or two pointers?

Use the hash set when the arrays are unsorted and memory is available: it does the least work. Use two pointers when both arrays already arrive sorted, or when memory is tight and you may sort them in place. The walk needs no set and produces the answer in order.

How do you keep repeated values in the intersection?

If a value should appear as often as it occurs in both arrays, so that [3, 1, 3, 3] and [3, 3] give [3, 3], replace the set with a count map. Count the values of nums1, and for each value of nums2 whose count is above zero, add it and lower its count. In the two-pointer walk, drop the check against the last value added.

How do you find the intersection when one array is too large for memory?

Build the hash set from the array that fits and read the large one in pieces, checking each value against the set and removing it on a match. Memory stays at the size of the smaller array. If neither array fits, sort both on disk and run the two-pointer walk over the sorted files.

Python

def intersection(nums1, nums2):
    # Write code here

Test cases

Case 1

Case 2

Input

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Expected

[4, 6]

Intersection of Two Arrays

Function

Constraints

Examples

Hints

Solution

Compare every pair

Sort both, then walk with two pointers

Hash set of the first array

Pitfalls and edge cases

Frequently asked questions4

Similar problems