Start learning free

LESSON 276 OF 441 · HASH TABLE

Intersection of Two Arrays in C#: O(n + m) with HashSet

Practice O(n + m) Read the full explanation

Given two integer arrays first and second, return an array of their intersection. Each element in the result must be unique, and the result must be sorted in ascending order.

 

Example 1:

Input: first = [1,2,2,1], second = [2,2]
Output: [2]

Example 2:

Input: first = [4,9,5], second = [9,4,9,8,4]
Output: [4,9]
Explanation: 4 and 9 are in both arrays. Each appears twice in second, but only once in the result.

 

Constraints:

  • 1 <= first.length, second.length <= 1000
  • -1000 <= first[i], second[i] <= 1000
Note:

Your algorithm should run in O(n + m) time, plus the time to sort the shared numbers, where n and m are the lengths of first and second.

STEP 1 OF 8
    Ctrl + Enter to check

    C# · HASH TABLE

    Intersection Of Two Arrays in C#, explained

    Problem overview

    The method Intersection receives two int[] arrays, first and second. It returns an int[] with the numbers that appear in both, each listed once, in ascending order. Each array has between 1 and 1000 items, with values from -1000 to 1000.

    For first = [1, 2, 2, 1] and second = [2, 2], the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4], it is [4, 9]: both numbers occur in both arrays, and although each appears twice in second, the result lists it once.

    Approach: remember one array in a set

    The brute-force approach checks every item of second against every item of first, which takes O(n × m) time. The slow part is the question "is this number in the first array?", asked once per item of the second.

    A HashSet<int> answers that question in constant time on average. It also stores each number once, which takes care of the duplicates in the input. So the plan is:

    1. Put every number of first in a set called seen.
    2. Go through second. Each number that seen contains goes into a second set, intersectionSet. The second set keeps a number once even when second repeats it.
    3. A set has no useful order, so sort its numbers and return them as an array.

    Here it is on first = [4, 9, 5] and second = [9, 4, 9, 8, 4]. After the first loop, seen holds 4, 9 and 5. The second loop checks 9 (in seen, so it is added), 4 (added), 9 again (already in intersectionSet, so nothing changes), 8 (not in seen, skipped) and 4 again (nothing changes). The shared numbers are 9 and 4, and sorting them gives [4, 9].

    The value range, -1000 to 1000, would also allow a bool[2001] indexed by value + 1000 instead of a set. The set works for any range of integers and doesn't depend on the constraint, so it is the more general tool.

    Step by step

    1. Name the inputs. int[] nums1 = first; and int[] nums2 = second; are shorter names for the same arrays. Nothing is copied: both names refer to the original array.
    2. Create seen as an empty HashSet<int>. It will hold the numbers of nums1.
    3. Loop over nums1 with foreach (int i in nums1).
    4. Add each number with seen.Add(i). Adding a number that is already in the set changes nothing, so repeated numbers need no special care.
    5. Create intersectionSet as a second empty HashSet<int>. It collects the shared numbers.
    6. Loop over nums2 with foreach (int i in nums2).
    7. Keep the shared numbers. If seen.Contains(i), add i to intersectionSet. A number that occurs twice in nums2 is stored once.
    8. Sort and convert. intersectionSet.OrderBy(x => x) produces the numbers in ascending order, and ToArray() turns the result into an int[], the type the method returns.

    The solution in C#

    class Solution {
    public int[] Intersection(int[] first, int[] second) {
        int[] nums1 = first;
        int[] nums2 = second;
        HashSet<int> seen = new HashSet<int>();
        foreach (int i in nums1) {
            seen.Add(i);
        }
        HashSet<int> intersectionSet = new HashSet<int>();
        foreach (int i in nums2) {
            if (seen.Contains(i)) {
                intersectionSet.Add(i);
            }
        }
        return intersectionSet.OrderBy(x => x).ToArray();
    }
}

    The C# details worth knowing:

    • A set is not ordered. The order in which a HashSet hands out its items is not part of its contract, so the code never relies on it. The sort at the end is what guarantees ascending output.
    • Add returns a bool. It gives true when the number was new and false when the set already held it. The lesson ignores the result, because only the final contents matter.
    • OrderBy and ToArray are LINQ. They come from System.Linq, and HashSet is in System.Collections.Generic. A standalone file needs a using line for each. OrderBy(x => x) takes a lambda that picks the sort key: here the number itself.
    • The result is a new array. ToArray() copies the sorted numbers, so changing the returned array doesn't affect either input.
    • Reusing the name i. Both loops declare int i. That is allowed because each variable lives only inside its own loop.
    • When nothing is shared, the set is empty and the method returns an empty array, not null.

    Complexity

    Let n and m be the lengths of first and second, and let u be the number of shared values.

    Time: O(n + m + u log u). Building seen takes n additions and scanning second takes m lookups, each constant on average. Sorting the u shared values adds u log u. That is the lesson's O(n + m) plus the time to sort the shared numbers.

    Space: O(n + m). seen holds up to n numbers, and intersectionSet and the returned array hold at most min(n, m).

    Edge cases and common mistakes

    • Duplicates. [1, 2, 2, 1] and [2, 2] gives [2], not [2, 2]. The second set collapses repeats.
    • No shared numbers. [1] and [2] gives [].
    • Negative numbers. [-3, 5, -3, 0] and [0, -3, 7] gives [-3, 0]. They sort like any other int.
    • Skipping the sort. The shared numbers would come out in whatever order the set provides, which the code can't depend on. The tests expect ascending order.
    • Using a list instead of a set. List<int>.Contains scans the whole list, which brings the time back to O(n × m).
    • Returning the HashSet itself. The method returns int[], so the set must be converted.

    Testing

    • [1, 2, 2, 1], [2, 2] gives [2].
    • [4, 9, 5], [9, 4, 9, 8, 4] gives [4, 9].
    • [1], [2] gives [].
    • [-3, 5, -3, 0], [0, -3, 7] gives [-3, 0].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free