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, plus O(k log k) to sort the answer, and O(n) space. Sorting both arrays and walking them 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.

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

Each shared value goes in the answer once, however often it repeats, and the answer must be sorted. 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

For each value of nums1, scan nums2 and stop at the first match. Skip a value already in the answer, so [8, 8, 8, 8] against [8, 8] gives one 8, and sort the answer at the end. A value goes in exactly when some copy of it finds a match, and the skip keeps it to once. Each value may scan all of nums2: with 5000 values in each array that is up to 2.5 × 10^7 comparisons, and when few values match, 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]. Move the pointer on the smaller value: it cannot match anything further along the other array, where every value is at least as large. Equal values are shared, so add the value and move both pointers. A value repeated on both sides, like 2 in [2, 2, 3] and [2, 2], matches twice; comparing with the last value added keeps one copy. The answer comes out sorted.

Sorting costs O(n log n + m log m) and the walk O(n + m), since every step moves a pointer. Sorting copies takes O(n + m) memory; sorting in place, as the C code does, leaves only 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 repeated 2 collapses, leaving {6, 2, 9, 4}. Walk nums2 and look up each value in constant time, removing a value from the set the moment it matches: the first 4 goes in the answer, and the second finds nothing. Every value added is in both arrays, and every shared value is added at its first copy in nums2.

The walk takes O(n + m) on average. The answer follows the order of nums2, so sort its k ≤ min(n, m) values in O(k log k). C has no built-in set, so the C code uses a flag array indexed by value + 10^5.

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

Adding a value every time it matches. [2, 2, 3, 3, 3] and [3, 2, 2] give [2, 3], not [3, 2, 2].
Returning values in the order you found them. The hash set walk follows nums2, so [7, -3] must be sorted to [-3, 7]. Python's set(nums1) & set(nums2) needs sorted too.
Sorting numbers as text. JavaScript's sort() without a comparator keeps [100000, 99] in that order. Pass (x, y) => x - y.
Indexing a flag array by the raw value. -3 is not a valid index; shift every value by 10^5.

Frequently asked questions3

What is the time complexity of Intersection of Two Arrays?

With a hash set, finding the shared values takes O(n + m) on average, plus O(k log k) to sort the answer, and O(n) space. Sorting both arrays and walking them 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 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?

When a value should appear as often as it occurs in both arrays, so [3, 1, 3, 3] and [3, 3] give [3, 3], count nums1 in a map. For each value of nums2 with a count above zero, add it and lower the count. The two-pointer walk only drops its check against the last value added.

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

Test #1

Test #2

Arguments

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

Expected Output

[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 questions3

Similar problems